Mercurial > hg > truffle
changeset 20827:5bf195ce816a
New partial evaluator that works on encoded graphs (instead of on bytecodes)
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/Fields.java Wed Apr 08 22:07:50 2015 -0700 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/Fields.java Wed Apr 08 22:38:40 2015 -0700 @@ -178,6 +178,38 @@ } /** + * Gets the value of a field for a given object. + * + * @param object the object whose field is to be read + * @param index the index of the field (between 0 and {@link #getCount()}) + * @return the value of the specified field which will be boxed if the field type is primitive + */ + public long getRawPrimitive(Object object, int index) { + long offset = offsets[index]; + Class<?> type = types[index]; + + if (type == Integer.TYPE) { + return unsafe.getInt(object, offset); + } else if (type == Long.TYPE) { + return unsafe.getLong(object, offset); + } else if (type == Boolean.TYPE) { + return unsafe.getBoolean(object, offset) ? 1 : 0; + } else if (type == Float.TYPE) { + return Float.floatToRawIntBits(unsafe.getFloat(object, offset)); + } else if (type == Double.TYPE) { + return Double.doubleToRawLongBits(unsafe.getDouble(object, offset)); + } else if (type == Short.TYPE) { + return unsafe.getShort(object, offset); + } else if (type == Character.TYPE) { + return unsafe.getChar(object, offset); + } else if (type == Byte.TYPE) { + return unsafe.getByte(object, offset); + } else { + throw GraalInternalError.shouldNotReachHere(); + } + } + + /** * Determines if a field in the domain of this object is the same as the field denoted by the * same index in another {@link Fields} object. */ @@ -244,6 +276,30 @@ } } + public void setRawPrimitive(Object object, int index, long value) { + long offset = offsets[index]; + Class<?> type = types[index]; + if (type == Integer.TYPE) { + unsafe.putInt(object, offset, (int) value); + } else if (type == Long.TYPE) { + unsafe.putLong(object, offset, value); + } else if (type == Boolean.TYPE) { + unsafe.putBoolean(object, offset, value != 0); + } else if (type == Float.TYPE) { + unsafe.putFloat(object, offset, Float.intBitsToFloat((int) value)); + } else if (type == Double.TYPE) { + unsafe.putDouble(object, offset, Double.longBitsToDouble(value)); + } else if (type == Short.TYPE) { + unsafe.putShort(object, offset, (short) value); + } else if (type == Character.TYPE) { + unsafe.putChar(object, offset, (char) value); + } else if (type == Byte.TYPE) { + unsafe.putByte(object, offset, (byte) value); + } else { + throw GraalInternalError.shouldNotReachHere(); + } + } + @Override public String toString() { StringBuilder sb = new StringBuilder(getClass().getSimpleName()).append('[');
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/util/FrequencyEncoder.java Wed Apr 08 22:38:40 2015 -0700 @@ -0,0 +1,118 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.compiler.common.util; + +import java.util.*; + +/** + * Creates an array of T objects order by the occurrence frequency of each object. The most + * frequently used object is the first one, the least frequently used the last one. If {@code null} + * is added, it is always the first element. + * + * Either object {@link #createIdentityEncoder() identity} or object + * {@link #createEqualityEncoder() equality} can be used to build the array and count the frequency. + */ +public class FrequencyEncoder<T> { + + static class Entry<T> { + protected final T object; + protected int frequency; + protected int index; + + protected Entry(T object) { + this.object = object; + this.index = -1; + } + } + + protected final Map<T, Entry<T>> map; + + /** + * Creates an encoder that uses object identity. + */ + public static <T> FrequencyEncoder<T> createIdentityEncoder() { + return new FrequencyEncoder<>(new IdentityHashMap<>()); + } + + /** + * Creates an encoder that uses {@link Object#equals(Object) object equality}. + */ + public static <T> FrequencyEncoder<T> createEqualityEncoder() { + return new FrequencyEncoder<>(new HashMap<>()); + } + + protected FrequencyEncoder(Map<T, Entry<T>> map) { + this.map = map; + } + + /** + * Adds an object to the array. + */ + public void addObject(T object) { + Entry<T> entry = map.get(object); + if (entry == null) { + entry = new Entry<>(object); + map.put(object, entry); + } + if (object == null) { + /* null must get index 0, so sort it up. */ + entry.frequency = Integer.MAX_VALUE; + } else { + entry.frequency++; + } + } + + /** + * Returns the index of an object in the array. The object must have been + * {@link #addObject(Object) added} before. + */ + public int getIndex(Object object) { + Entry<T> entry = map.get(object); + assert entry != null && entry.index >= 0; + return entry.index; + } + + /** + * Returns the number of distinct objects that have been added, i.e., the length of the array. + */ + public int getLength() { + return map.size(); + } + + /** + * Fills the provided array with the added objects. The array must have the {@link #getLength() + * correct length}. + */ + public T[] encodeAll(T[] allObjects) { + assert allObjects.length == map.size(); + List<Entry<T>> sortedEntries = new ArrayList<>(map.values()); + sortedEntries.sort((e1, e2) -> -Integer.compare(e1.frequency, e2.frequency)); + for (int i = 0; i < sortedEntries.size(); i++) { + Entry<T> entry = sortedEntries.get(i); + entry.index = i; + allObjects[i] = entry.object; + assert entry.object != null || entry.index == 0; + } + return allObjects; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/util/TypeConversion.java Wed Apr 08 22:38:40 2015 -0700 @@ -0,0 +1,84 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.compiler.common.util; + +/** + * Provides low-level value checks and conversion for signed and unsigned values of size 1, 2, and 4 + * bytes. + */ +public class TypeConversion { + + public static boolean isS1(long value) { + return value >= Byte.MIN_VALUE && value <= Byte.MAX_VALUE; + } + + public static boolean isU1(long value) { + return value >= 0 && value <= 0xFF; + } + + public static boolean isS2(long value) { + return value >= Short.MIN_VALUE && value <= Short.MAX_VALUE; + } + + public static boolean isU2(long value) { + return value >= 0 && value <= 0xFFFF; + } + + public static boolean isS4(long value) { + return value >= Integer.MIN_VALUE && value <= Integer.MAX_VALUE; + } + + public static boolean isU4(long value) { + return value >= 0 && value <= 0xFFFFFFFFL; + } + + public static byte asS1(long value) { + assert isS1(value); + return (byte) value; + } + + public static byte asU1(long value) { + assert isU1(value); + return (byte) value; + } + + public static short asS2(long value) { + assert isS2(value); + return (short) value; + } + + public static short asU2(long value) { + assert isU2(value); + return (short) value; + } + + public static int asS4(long value) { + assert isS4(value); + return (int) value; + } + + public static int asU4(long value) { + assert isU4(value); + return (int) value; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/util/TypeReader.java Wed Apr 08 22:38:40 2015 -0700 @@ -0,0 +1,108 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.compiler.common.util; + +/** + * Provides low-level read access for signed and unsigned values of size 1, 2, 4, and 8 bytes. + */ +public interface TypeReader { + + /** Returns the next byte index to be read. */ + long getByteIndex(); + + /** Sets the next byte index to be read. */ + void setByteIndex(long byteIndex); + + /** Reads a signed 1 byte value. */ + int getS1(); + + /** Reads an unsigned 1 byte value. */ + int getU1(); + + /** Reads a signed 2 byte value. */ + int getS2(); + + /** Reads an unsigned 2 byte value. */ + int getU2(); + + /** Reads a signed 4 byte value. */ + int getS4(); + + /** Reads an unsigned 4 byte value. */ + long getU4(); + + /** Reads a signed 4 byte value. */ + long getS8(); + + /** + * Reads a signed value that has been written using {@link TypeWriter#putSV variable byte size + * encoding}. + */ + default long getSV() { + long result = 0; + int shift = 0; + long b; + do { + b = getU1(); + result |= (b & 0x7f) << shift; + shift += 7; + } while ((b & 0x80) != 0); + + if ((b & 0x40) != 0 && shift < 64) { + result |= -1L << shift; + } + return result; + } + + /** + * Reads a signed variable byte size encoded value that is known to fit into the range of int. + */ + default int getSVInt() { + return TypeConversion.asS4(getSV()); + } + + /** + * Reads an unsigned value that has been written using {@link TypeWriter#putSV variable byte + * size encoding}. + */ + default long getUV() { + long result = 0; + int shift = 0; + long b; + do { + b = getU1(); + result |= (b & 0x7f) << shift; + shift += 7; + } while ((b & 0x80) != 0); + + return result; + } + + /** + * Reads an unsigned variable byte size encoded value that is known to fit into the range of + * int. + */ + default int getUVInt() { + return TypeConversion.asS4(getUV()); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/util/TypeWriter.java Wed Apr 08 22:38:40 2015 -0700 @@ -0,0 +1,88 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.compiler.common.util; + +/** + * Provides low-level sequential write access for signed and unsigned values of size 1, 2, 4, and 8 + * bytes. + */ +public interface TypeWriter { + + /** + * Returns the number of bytes that have been written, i.e., the byte index of the next byte to + * be written. + */ + long getBytesWritten(); + + /** Writes a signed 1 byte value. */ + void putS1(long value); + + /** Writes an unsigned 1 byte value. */ + void putU1(long value); + + /** Writes a signed 2 byte value. */ + void putS2(long value); + + /** Writes an unsigned 2 byte value. */ + void putU2(long value); + + /** Writes a signed 4 byte value. */ + void putS4(long value); + + /** Writes an unsigned 4 byte value. */ + void putU4(long value); + + /** Writes a signed 8 byte value. */ + void putS8(long value); + + /** + * Writes a signed value in a variable byte size encoding. + */ + default void putSV(long value) { + long cur = value; + while (true) { + if (cur >= -64 && cur < 64) { + putU1(cur & 0x7f); + return; + } + putU1(0x80 | (cur & 0x7f)); + cur = cur >> 7; + } + } + + /** + * Writes an unsigned value in a variable byte size encoding. + */ + default void putUV(long value) { + long cur = value; + while (true) { + assert cur >= 0; + if (cur < 128) { + putU1(cur & 0x7f); + return; + } + putU1(0x80 | (cur & 0x7f)); + cur = cur >> 7; + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/util/UnsafeArrayTypeReader.java Wed Apr 08 22:38:40 2015 -0700 @@ -0,0 +1,138 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.compiler.common.util; + +import sun.misc.*; + +import com.oracle.graal.compiler.common.*; + +/** + * Provides low-level read access from a byte[] array for signed and unsigned values of size 1, 2, + * 4, and 8 bytes. + */ +public class UnsafeArrayTypeReader implements TypeReader { + + public static int getS1(byte[] data, long byteIndex) { + return UnsafeAccess.unsafe.getByte(data, readOffset(data, byteIndex, Byte.BYTES)); + } + + public static int getU1(byte[] data, long byteIndex) { + return UnsafeAccess.unsafe.getByte(data, readOffset(data, byteIndex, Byte.BYTES)) & 0xFF; + } + + public static int getS2(byte[] data, long byteIndex) { + return UnsafeAccess.unsafe.getShort(data, readOffset(data, byteIndex, Short.BYTES)); + } + + public static int getU2(byte[] data, long byteIndex) { + return UnsafeAccess.unsafe.getShort(data, readOffset(data, byteIndex, Short.BYTES)) & 0xFFFF; + } + + public static int getS4(byte[] data, long byteIndex) { + return UnsafeAccess.unsafe.getInt(data, readOffset(data, byteIndex, Integer.BYTES)); + } + + public static long getU4(byte[] data, long byteIndex) { + return UnsafeAccess.unsafe.getInt(data, readOffset(data, byteIndex, Integer.BYTES)) & 0xFFFFFFFFL; + } + + public static long getLong(byte[] data, long byteIndex) { + return UnsafeAccess.unsafe.getLong(data, readOffset(data, byteIndex, Long.BYTES)); + } + + private static long readOffset(byte[] data, long byteIndex, int numBytes) { + assert byteIndex >= 0; + assert numBytes > 0; + assert byteIndex + numBytes <= data.length; + assert Unsafe.ARRAY_BYTE_INDEX_SCALE == 1; + + return byteIndex + Unsafe.ARRAY_BYTE_BASE_OFFSET; + } + + private final byte[] data; + private long byteIndex; + + public UnsafeArrayTypeReader(byte[] data, long byteIndex) { + this.data = data; + this.byteIndex = byteIndex; + } + + @Override + public long getByteIndex() { + return byteIndex; + } + + @Override + public void setByteIndex(long byteIndex) { + this.byteIndex = byteIndex; + } + + @Override + public int getS1() { + int result = getS1(data, byteIndex); + byteIndex += Byte.BYTES; + return result; + } + + @Override + public int getU1() { + int result = getU1(data, byteIndex); + byteIndex += Byte.BYTES; + return result; + } + + @Override + public int getS2() { + int result = getS2(data, byteIndex); + byteIndex += Short.BYTES; + return result; + } + + @Override + public int getU2() { + int result = getU2(data, byteIndex); + byteIndex += Short.BYTES; + return result; + } + + @Override + public int getS4() { + int result = getS4(data, byteIndex); + byteIndex += Integer.BYTES; + return result; + } + + @Override + public long getU4() { + long result = getU4(data, byteIndex); + byteIndex += Integer.BYTES; + return result; + } + + @Override + public long getS8() { + long result = getLong(data, byteIndex); + byteIndex += Long.BYTES; + return result; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/util/UnsafeArrayTypeWriter.java Wed Apr 08 22:38:40 2015 -0700 @@ -0,0 +1,130 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.compiler.common.util; + +import sun.misc.*; + +import com.oracle.graal.compiler.common.*; + +/** + * Provides low-level sequential write access to a byte[] array for signed and unsigned values of + * size 1, 2, 4, and 8 bytes. To avoid copying an array when the buffer size is no longer + * sufficient, the buffer is split into chunks of a fixed size. + */ +public class UnsafeArrayTypeWriter implements TypeWriter { + + private static final int CHUNK_SIZE = 4000; + + static class Chunk { + protected final byte[] data = new byte[CHUNK_SIZE]; + protected int size; + protected Chunk next; + } + + private Chunk firstChunk; + private Chunk writeChunk; + private int totalSize; + + public UnsafeArrayTypeWriter() { + firstChunk = new Chunk(); + writeChunk = firstChunk; + } + + @Override + public long getBytesWritten() { + return totalSize; + } + + /** + * Copies the buffer into the provided byte[] array of length {@link #getBytesWritten()}. + */ + public byte[] toArray(byte[] result) { + assert result.length == totalSize; + int resultIdx = 0; + for (Chunk cur = firstChunk; cur != null; cur = cur.next) { + System.arraycopy(cur.data, 0, result, resultIdx, cur.size); + resultIdx += cur.size; + } + assert resultIdx == totalSize; + return result; + } + + @Override + public void putS1(long value) { + long offset = writeOffset(Byte.BYTES); + UnsafeAccess.unsafe.putByte(writeChunk.data, offset, TypeConversion.asS1(value)); + } + + @Override + public void putU1(long value) { + long offset = writeOffset(Byte.BYTES); + UnsafeAccess.unsafe.putByte(writeChunk.data, offset, TypeConversion.asU1(value)); + } + + @Override + public void putS2(long value) { + long offset = writeOffset(Short.BYTES); + UnsafeAccess.unsafe.putShort(writeChunk.data, offset, TypeConversion.asS2(value)); + } + + @Override + public void putU2(long value) { + long offset = writeOffset(Short.BYTES); + UnsafeAccess.unsafe.putShort(writeChunk.data, offset, TypeConversion.asU2(value)); + } + + @Override + public void putS4(long value) { + long offset = writeOffset(Integer.BYTES); + UnsafeAccess.unsafe.putInt(writeChunk.data, offset, TypeConversion.asS4(value)); + } + + @Override + public void putU4(long value) { + long offset = writeOffset(Integer.BYTES); + UnsafeAccess.unsafe.putInt(writeChunk.data, offset, TypeConversion.asU4(value)); + } + + @Override + public void putS8(long value) { + long offset = writeOffset(Long.BYTES); + UnsafeAccess.unsafe.putLong(writeChunk.data, offset, value); + } + + private long writeOffset(int writeBytes) { + if (writeChunk.size + writeBytes >= writeChunk.data.length) { + Chunk newChunk = new Chunk(); + writeChunk.next = newChunk; + writeChunk = newChunk; + } + + assert Unsafe.ARRAY_BYTE_INDEX_SCALE == 1; + long result = writeChunk.size + Unsafe.ARRAY_BYTE_BASE_OFFSET; + + totalSize += writeBytes; + writeChunk.size += writeBytes; + assert writeChunk.size <= writeChunk.data.length; + + return result; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraphEncoderTest.java Wed Apr 08 22:38:40 2015 -0700 @@ -0,0 +1,79 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.compiler.test; + +import java.lang.reflect.*; +import java.util.*; + +import org.junit.*; + +import com.oracle.graal.api.meta.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.StructuredGraph.AllowAssumptions; +import com.oracle.graal.phases.common.*; +import com.oracle.graal.phases.tiers.*; + +public class GraphEncoderTest extends GraalCompilerTest { + + @Test + public void test01() { + testStringMethods(false); + } + + @Test + public void test02() { + testStringMethods(true); + } + + public void testStringMethods(boolean canonicalize) { + /* Encode and decode all methods of java.lang.String. */ + List<StructuredGraph> originalGraphs = new ArrayList<>(); + for (Method method : String.class.getDeclaredMethods()) { + ResolvedJavaMethod javaMethod = getMetaAccess().lookupJavaMethod(method); + if (javaMethod.hasBytecodes()) { + StructuredGraph originalGraph = parseEager(javaMethod, AllowAssumptions.YES); + if (canonicalize) { + PhaseContext context = new PhaseContext(getProviders()); + new CanonicalizerPhase().apply(originalGraph, context); + } + originalGraphs.add(originalGraph); + } + } + + GraphEncoder encoder = new GraphEncoder(); + for (StructuredGraph originalGraph : originalGraphs) { + encoder.prepare(originalGraph); + } + encoder.finishPrepare(); + Map<StructuredGraph, Long> startOffsets = new HashMap<>(); + for (StructuredGraph originalGraph : originalGraphs) { + startOffsets.put(originalGraph, encoder.encode(originalGraph)); + } + + for (StructuredGraph originalGraph : originalGraphs) { + EncodedGraph encodedGraph = new EncodedGraph(encoder.getEncoding(), startOffsets.get(originalGraph), encoder.getObjects(), encoder.getNodeClasses(), originalGraph.getAssumptions(), + originalGraph.getInlinedMethods()); + GraphEncoder.verifyEncoding(originalGraph, encodedGraph); + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/TypeWriterTest.java Wed Apr 08 22:38:40 2015 -0700 @@ -0,0 +1,165 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.compiler.test; + +import org.junit.*; + +import com.oracle.graal.compiler.common.util.*; + +public class TypeWriterTest { + + private static void putValue(TypeWriter writer, long value) { + if (TypeConversion.isS1(value)) { + writer.putS1(value); + } + if (TypeConversion.isU1(value)) { + writer.putU1(value); + } + if (TypeConversion.isS2(value)) { + writer.putS2(value); + } + if (TypeConversion.isU2(value)) { + writer.putU2(value); + } + if (TypeConversion.isS4(value)) { + writer.putS4(value); + } + if (TypeConversion.isU4(value)) { + writer.putU4(value); + } + writer.putS8(value); + writer.putSV(value); + if (value >= 0) { + writer.putUV(value); + } + } + + private static void checkValue(TypeReader reader, long value) { + if (TypeConversion.isS1(value)) { + Assert.assertEquals(value, reader.getS1()); + } + if (TypeConversion.isU1(value)) { + Assert.assertEquals(value, reader.getU1()); + } + if (TypeConversion.isS2(value)) { + Assert.assertEquals(value, reader.getS2()); + } + if (TypeConversion.isU2(value)) { + Assert.assertEquals(value, reader.getU2()); + } + if (TypeConversion.isS4(value)) { + Assert.assertEquals(value, reader.getS4()); + } + if (TypeConversion.isU4(value)) { + Assert.assertEquals(value, reader.getU4()); + } + Assert.assertEquals(value, reader.getS8()); + Assert.assertEquals(value, reader.getSV()); + if (value >= 0) { + Assert.assertEquals(value, reader.getUV()); + } + } + + private static void putValues(TypeWriter writer) { + for (int i = 0; i < 64; i++) { + long value = 1L << i; + putValue(writer, value - 2); + putValue(writer, value - 1); + putValue(writer, value); + putValue(writer, value + 1); + putValue(writer, value + 2); + + putValue(writer, -value - 2); + putValue(writer, -value - 1); + putValue(writer, -value); + putValue(writer, -value + 1); + putValue(writer, -value + 2); + } + } + + private static void checkValues(TypeReader reader) { + for (int i = 0; i < 64; i++) { + long value = 1L << i; + checkValue(reader, value - 2); + checkValue(reader, value - 1); + checkValue(reader, value); + checkValue(reader, value + 1); + checkValue(reader, value + 2); + + checkValue(reader, -value - 2); + checkValue(reader, -value - 1); + checkValue(reader, -value); + checkValue(reader, -value + 1); + checkValue(reader, -value + 2); + } + } + + @Test + public void test01() { + UnsafeArrayTypeWriter writer = new UnsafeArrayTypeWriter(); + putValues(writer); + + byte[] array = new byte[(int) writer.getBytesWritten()]; + writer.toArray(array); + UnsafeArrayTypeReader reader = new UnsafeArrayTypeReader(array, 0); + checkValues(reader); + } + + private static void checkSignedSize(TypeWriter writer, long value, int expectedSize) { + long sizeBefore = writer.getBytesWritten(); + writer.putSV(value); + Assert.assertEquals(expectedSize, writer.getBytesWritten() - sizeBefore); + } + + private static void checkUnsignedSize(TypeWriter writer, long value, int expectedSize) { + long sizeBefore = writer.getBytesWritten(); + writer.putUV(value); + Assert.assertEquals(expectedSize, writer.getBytesWritten() - sizeBefore); + } + + private static void checkSizes(TypeWriter writer) { + checkSignedSize(writer, 0, 1); + checkSignedSize(writer, 63, 1); + checkSignedSize(writer, -64, 1); + checkSignedSize(writer, 64, 2); + checkSignedSize(writer, -65, 2); + checkSignedSize(writer, 8191, 2); + checkSignedSize(writer, -8192, 2); + checkSignedSize(writer, 8192, 3); + checkSignedSize(writer, -8193, 3); + checkSignedSize(writer, Long.MAX_VALUE, 10); + checkSignedSize(writer, Long.MIN_VALUE, 10); + + checkUnsignedSize(writer, 0, 1); + checkUnsignedSize(writer, 127, 1); + checkUnsignedSize(writer, 128, 2); + checkUnsignedSize(writer, 16383, 2); + checkUnsignedSize(writer, 16384, 3); + checkUnsignedSize(writer, Long.MAX_VALUE, 9); + } + + @Test + public void test02() { + checkSizes(new UnsafeArrayTypeWriter()); + } +}
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Edges.java Wed Apr 08 22:07:50 2015 -0700 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Edges.java Wed Apr 08 22:38:40 2015 -0700 @@ -263,7 +263,7 @@ update(node, old, value); } - protected abstract void update(Node node, Node oldValue, Node newValue); + public abstract void update(Node node, Node oldValue, Node newValue); public boolean contains(Node node, Node value) { final long[] curOffsets = this.offsets;
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/InputEdges.java Wed Apr 08 22:07:50 2015 -0700 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/InputEdges.java Wed Apr 08 22:38:40 2015 -0700 @@ -60,7 +60,7 @@ } @Override - protected void update(Node node, Node oldValue, Node newValue) { + public void update(Node node, Node oldValue, Node newValue) { node.updateUsages(oldValue, newValue); } }
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java Wed Apr 08 22:07:50 2015 -0700 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java Wed Apr 08 22:38:40 2015 -0700 @@ -209,12 +209,12 @@ public static final int NOT_ITERABLE = -1; public Node(NodeClass<? extends Node> c) { - init(); + init(c); + } + + final void init(NodeClass<? extends Node> c) { assert c.getJavaClass() == this.getClass(); this.nodeClass = c; - } - - final void init() { id = INITIAL_ID; extraUsages = NO_NODES; }
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java Wed Apr 08 22:07:50 2015 -0700 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java Wed Apr 08 22:38:40 2015 -0700 @@ -23,6 +23,7 @@ package com.oracle.graal.graph; import static com.oracle.graal.compiler.common.Fields.*; +import static com.oracle.graal.compiler.common.GraalInternalError.*; import static com.oracle.graal.graph.Edges.*; import static com.oracle.graal.graph.InputEdges.*; import static com.oracle.graal.graph.Node.*; @@ -663,22 +664,16 @@ } /** - * Initializes a fresh allocated node for which no constructor is called yet. Needed to - * implement node factories in svm. + * Returns a newly allocated node for which no subclass-specific constructor has been called. */ - public void initRawNode(Node node) { - node.init(); - initNullEdgeLists(node, Edges.Type.Inputs); - initNullEdgeLists(node, Edges.Type.Successors); - } - - private void initNullEdgeLists(Node node, Edges.Type type) { - Edges edges = getEdges(type); - final long[] curOffsets = edges.getOffsets(); - for (int inputPos = edges.getDirectCount(); inputPos < edges.getCount(); inputPos++) { - if (Edges.getNodeList(node, curOffsets, inputPos) == null) { - Edges.initializeList(node, curOffsets, inputPos, type == Edges.Type.Inputs ? new NodeInputList<>(node) : new NodeSuccessorList<>(node)); - } + @SuppressWarnings("unchecked") + public Node allocateInstance() { + try { + Node node = (Node) UnsafeAccess.unsafe.allocateInstance(getJavaClass()); + node.init((NodeClass<? extends Node>) this); + return node; + } catch (InstantiationException ex) { + throw shouldNotReachHere(ex); } }
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/SuccessorEdges.java Wed Apr 08 22:07:50 2015 -0700 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/SuccessorEdges.java Wed Apr 08 22:38:40 2015 -0700 @@ -35,7 +35,7 @@ } @Override - protected void update(Node node, Node oldValue, Node newValue) { + public void update(Node node, Node oldValue, Node newValue) { node.updatePredecessor(oldValue, newValue); } }
--- a/graal/com.oracle.graal.graphbuilderconf/src/com/oracle/graal/graphbuilderconf/GraphBuilderContext.java Wed Apr 08 22:07:50 2015 -0700 +++ b/graal/com.oracle.graal.graphbuilderconf/src/com/oracle/graal/graphbuilderconf/GraphBuilderContext.java Wed Apr 08 22:38:40 2015 -0700 @@ -22,12 +22,19 @@ */ package com.oracle.graal.graphbuilderconf; +import static com.oracle.graal.api.meta.DeoptimizationAction.*; +import static com.oracle.graal.api.meta.DeoptimizationReason.*; +import static com.oracle.graal.compiler.common.type.StampFactory.*; + import com.oracle.graal.api.code.*; import com.oracle.graal.api.meta.*; import com.oracle.graal.api.replacements.*; +import com.oracle.graal.compiler.common.type.*; import com.oracle.graal.nodes.CallTargetNode.InvokeKind; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.type.*; /** * Used by a {@link GraphBuilderPlugin} to interface with a graph builder object. @@ -222,7 +229,7 @@ * Determines if the current parsing context is a snippet or method substitution. */ default boolean parsingReplacement() { - return getReplacement() == null; + return getReplacement() != null; } /** @@ -232,4 +239,27 @@ Replacement getReplacement(); BailoutException bailout(String string); + + /** + * Gets a version of a given value that has a {@linkplain StampTool#isPointerNonNull(ValueNode) + * non-null} stamp. + */ + default ValueNode nullCheckedValue(ValueNode value) { + if (!StampTool.isPointerNonNull(value.stamp())) { + IsNullNode condition = getGraph().unique(new IsNullNode(value)); + ObjectStamp receiverStamp = (ObjectStamp) value.stamp(); + Stamp stamp = receiverStamp.join(objectNonNull()); + FixedGuardNode fixedGuard = append(new FixedGuardNode(condition, NullCheckException, InvalidateReprofile, true)); + PiNode nonNullReceiver = getGraph().unique(new PiNode(value, stamp)); + nonNullReceiver.setGuard(fixedGuard); + // TODO: Propogating the non-null into the frame state would + // remove subsequent null-checks on the same value. However, + // it currently causes an assertion failure when merging states. + // + // frameState.replace(value, nonNullReceiver); + return nonNullReceiver; + } + return value; + } + }
--- a/graal/com.oracle.graal.graphbuilderconf/src/com/oracle/graal/graphbuilderconf/InvocationPlugins.java Wed Apr 08 22:07:50 2015 -0700 +++ b/graal/com.oracle.graal.graphbuilderconf/src/com/oracle/graal/graphbuilderconf/InvocationPlugins.java Wed Apr 08 22:38:40 2015 -0700 @@ -63,6 +63,42 @@ } } + public static class InvocationPluginReceiver implements Receiver { + private final GraphBuilderContext parser; + private ValueNode[] args; + private ValueNode value; + + public InvocationPluginReceiver(GraphBuilderContext parser) { + this.parser = parser; + } + + @Override + public ValueNode get() { + assert args != null : "Cannot get the receiver of a static method"; + if (value == null) { + value = parser.nullCheckedValue(args[0]); + if (value != args[0]) { + args[0] = value; + } + } + return value; + } + + @Override + public boolean isConstant() { + return args[0].isConstant(); + } + + public InvocationPluginReceiver init(ResolvedJavaMethod targetMethod, ValueNode[] newArgs) { + if (!targetMethod.isStatic()) { + this.args = newArgs; + this.value = null; + return this; + } + return null; + } + } + /** * Utility for * {@linkplain InvocationPlugins#register(InvocationPlugin, Class, String, Class...)
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java Wed Apr 08 22:07:50 2015 -0700 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java Wed Apr 08 22:38:40 2015 -0700 @@ -50,7 +50,7 @@ import com.oracle.graal.graph.iterators.*; import com.oracle.graal.graphbuilderconf.*; import com.oracle.graal.graphbuilderconf.InlineInvokePlugin.InlineInfo; -import com.oracle.graal.graphbuilderconf.InvocationPlugins.Receiver; +import com.oracle.graal.graphbuilderconf.InvocationPlugins.InvocationPluginReceiver; import com.oracle.graal.java.AbstractBytecodeParser.ReplacementContext; import com.oracle.graal.java.BciBlockMapping.BciBlock; import com.oracle.graal.java.BciBlockMapping.ExceptionDispatchBlock; @@ -133,7 +133,7 @@ frameState.initializeForMethodStart(graphBuilderConfig.eagerResolving() || replacementContext != null, graphBuilderConfig.getPlugins().getParameterPlugin()); parser.build(graph.start(), frameState); - parser.connectLoopEndToBegin(); + connectLoopEndToBegin(graph); // Remove dead parameters. for (ParameterNode param : graph.getNodes(ParameterNode.TYPE)) { @@ -228,42 +228,6 @@ } } - static class InvocationPluginReceiver implements Receiver { - final BytecodeParser parser; - ValueNode[] args; - ValueNode value; - - public InvocationPluginReceiver(BytecodeParser parser) { - this.parser = parser; - } - - @Override - public ValueNode get() { - assert args != null : "Cannot get the receiver of a static method"; - if (value == null) { - value = parser.nullCheckedValue(args[0]); - if (value != args[0]) { - args[0] = value; - } - } - return value; - } - - @Override - public boolean isConstant() { - return args[0].isConstant(); - } - - InvocationPluginReceiver init(ResolvedJavaMethod targetMethod, ValueNode[] newArgs) { - if (!targetMethod.isStatic()) { - this.args = newArgs; - this.value = null; - return this; - } - return null; - } - } - public class BytecodeParser extends AbstractBytecodeParser implements GraphBuilderContext { private BciBlockMapping blockMap; @@ -417,28 +381,6 @@ } } - /** - * Gets a version of a given value that has a - * {@linkplain StampTool#isPointerNonNull(ValueNode) non-null} stamp. - */ - ValueNode nullCheckedValue(ValueNode value) { - if (!StampTool.isPointerNonNull(value.stamp())) { - IsNullNode condition = graph.unique(new IsNullNode(value)); - ObjectStamp receiverStamp = (ObjectStamp) value.stamp(); - Stamp stamp = receiverStamp.join(objectNonNull()); - FixedGuardNode fixedGuard = append(new FixedGuardNode(condition, NullCheckException, InvalidateReprofile, true)); - PiNode nonNullReceiver = graph.unique(new PiNode(value, stamp)); - nonNullReceiver.setGuard(fixedGuard); - // TODO: Propogating the non-null into the frame state would - // remove subsequent null-checks on the same value. However, - // it currently causes an assertion failure when merging states. - // - // frameState.replace(value, nonNullReceiver); - return nonNullReceiver; - } - return value; - } - private void detectLoops(FixedNode startInstruction) { NodeBitMap visited = graph.createNodeBitMap(); NodeBitMap active = graph.createNodeBitMap(); @@ -2023,30 +1965,6 @@ } } - /** - * Remove loop header without loop ends. This can happen with degenerated loops like - * this one: - * - * <pre> - * for (;;) { - * try { - * break; - * } catch (UnresolvedException iioe) { - * } - * } - * </pre> - */ - private void connectLoopEndToBegin() { - for (LoopBeginNode begin : graph.getNodes(LoopBeginNode.TYPE)) { - if (begin.loopEnds().isEmpty()) { - assert begin.forwardEndCount() == 1; - graph.reduceDegenerateLoopBegin(begin); - } else { - GraphUtil.normalizeLoopBegin(begin); - } - } - } - private void createUnwind() { assert frameState.stackSize() == 1 : frameState; ValueNode exception = frameState.apop(); @@ -2513,4 +2431,27 @@ assert assertionsEnabled = true; return assertionsEnabled; } + + /** + * Remove loop header without loop ends. This can happen with degenerated loops like this one: + * + * <pre> + * for (;;) { + * try { + * break; + * } catch (UnresolvedException iioe) { + * } + * } + * </pre> + */ + public static void connectLoopEndToBegin(StructuredGraph graph) { + for (LoopBeginNode begin : graph.getNodes(LoopBeginNode.TYPE)) { + if (begin.loopEnds().isEmpty()) { + assert begin.forwardEndCount() == 1; + graph.reduceDegenerateLoopBegin(begin); + } else { + GraphUtil.normalizeLoopBegin(begin); + } + } + } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/EncodedGraph.java Wed Apr 08 22:38:40 2015 -0700 @@ -0,0 +1,76 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.nodes; + +import java.util.*; + +import com.oracle.graal.api.meta.*; +import com.oracle.graal.graph.*; + +/** + * A {@link StructuredGraph} encoded in a compact binary representation as a byte[] array. See + * {@link GraphEncoder} for a description of the encoding format. Use {@link GraphDecoder} for + * decoding. + */ +public class EncodedGraph { + + private final byte[] encoding; + private final long startOffset; + private final Object[] objects; + private final NodeClass<?>[] types; + private final Assumptions assumptions; + private final Set<ResolvedJavaMethod> inlinedMethods; + + public EncodedGraph(byte[] encoding, long startOffset, Object[] objects, NodeClass<?>[] types, Assumptions assumptions, Set<ResolvedJavaMethod> inlinedMethods) { + this.encoding = encoding; + this.startOffset = startOffset; + this.objects = objects; + this.types = types; + this.assumptions = assumptions; + this.inlinedMethods = inlinedMethods; + } + + public byte[] getEncoding() { + return encoding; + } + + public long getStartOffset() { + return startOffset; + } + + public Object[] getObjects() { + return objects; + } + + public NodeClass<?>[] getNodeClasses() { + return types; + } + + public Assumptions getAssumptions() { + return assumptions; + } + + public Set<ResolvedJavaMethod> getInlinedMethods() { + return inlinedMethods; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/GraphDecoder.java Wed Apr 08 22:38:40 2015 -0700 @@ -0,0 +1,1033 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.nodes; + +import static com.oracle.graal.compiler.common.GraalInternalError.*; + +import java.util.*; + +import com.oracle.graal.compiler.common.*; +import com.oracle.graal.compiler.common.util.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.util.*; + +/** + * Decoder for {@link EncodedGraph encoded graphs} produced by {@link GraphEncoder}. Support for + * loop explosion during decoding is built into this class, because it requires many interactions + * with the decoding process. Subclasses can provide canonicalization and simplification of nodes + * during decoding, as well as method inlining during decoding. + */ +public class GraphDecoder { + + public enum LoopExplosionKind { + /** + * No loop explosion. + */ + NONE, + /** + * Fully unroll all loops. The loops must have a known finite number of iterations. If a + * loop has multiple loop ends, they are merged so that the subsequent loop iteration is + * processed only once. For example, a loop with 4 iterations and 2 loop ends leads to + * 1+1+1+1 = 4 copies of the loop body. The merge can introduce phi functions. + */ + FULL_UNROLL, + /** + * Fully explode all loops. The loops must have a known finite number of iterations. If a + * loop has multiple loop ends, they are not merged so that subsequent loop iterations are + * processed multiple times. For example, a loop with 4 iterations and 2 loop ends leads to + * 1+2+4+8 = 15 copies of the loop body. + */ + FULL_EXPLODE, + /** + * like {@link #FULL_EXPLODE}, but copies of the loop body that have the exact same state + * are merged. This reduces the number of copies necessary, but can introduce loops again. + */ + MERGE_EXPLODE + } + + /** Decoding state maintained for each encoded graph. */ + protected static class MethodScope { + /** The target graph where decoded nodes are added to. */ + public final StructuredGraph graph; + /** The state of the caller method. Only non-null during method inlining. */ + public final MethodScope caller; + /** The encode graph that is decoded. */ + public final EncodedGraph encodedGraph; + /** Access to the encoded graph. */ + public final TypeReader reader; + /** + * The "table of contents" of the encoded graph, i.e., the mapping from orderId numbers to + * the offset in the encoded byte[] array. + */ + public final long[] nodeStartOffsets; + /** The kind of loop explosion to be performed during decoding. */ + public final LoopExplosionKind loopExplosion; + + /** + * The start node of the decoded graph. This is a temporary node for inlined graphs that + * needs to be deleted after inlining. + */ + public StartNode startNode; + /** All return nodes encountered during decoding. */ + public final List<ReturnNode> returnNodes; + /** The exception unwind node encountered during decoding, or null. */ + public UnwindNode unwindNode; + + protected MethodScope(StructuredGraph graph, MethodScope caller, EncodedGraph encodedGraph, LoopExplosionKind loopExplosion) { + this.graph = graph; + this.caller = caller; + this.encodedGraph = encodedGraph; + this.loopExplosion = loopExplosion; + this.returnNodes = new ArrayList<>(); + + reader = new UnsafeArrayTypeReader(encodedGraph.getEncoding(), encodedGraph.getStartOffset()); + int nodeCount = reader.getUVInt(); + nodeStartOffsets = new long[nodeCount]; + for (int i = 0; i < nodeCount; i++) { + nodeStartOffsets[i] = encodedGraph.getStartOffset() - reader.getUV(); + } + } + + public boolean isInlinedMethod() { + return caller != null; + } + } + + /** Decoding state maintained for each loop in the encoded graph. */ + protected static class LoopScope { + public final LoopScope outer; + public final int loopDepth; + public final int loopIteration; + /** + * Upcoming loop iterations during loop explosions that have not been processed yet. Only + * used when {@link MethodScope#loopExplosion} is not {@link LoopExplosionKind#NONE}. + */ + public Deque<LoopScope> nextIterations; + /** + * Information about already processed loop iterations for state merging during loop + * explosion. Only used when {@link MethodScope#loopExplosion} is + * {@link LoopExplosionKind#MERGE_EXPLODE}. + */ + public final Map<LoopExplosionState, LoopExplosionState> iterationStates; + public final int loopBeginOrderId; + /** + * The worklist of fixed nodes to process. Since we already the correct processing order + * from the orderId, we just set the orderId bit in the bitset when a node is ready for + * processing. The lowest set bit is the next node to process. + */ + public final BitSet nodesToProcess; + /** Nodes that have been created, indexed by the orderId. */ + public final Node[] createdNodes; + /** + * Nodes that have been created in outer loop scopes and existed before starting to process + * this loop, indexed by the orderId. + */ + public final Node[] initialCreatedNodes; + + protected LoopScope(MethodScope methodScope) { + this.outer = null; + this.nextIterations = null; + this.loopDepth = 0; + this.loopIteration = 0; + this.iterationStates = null; + this.loopBeginOrderId = -1; + + int nodeCount = methodScope.nodeStartOffsets.length; + this.nodesToProcess = new BitSet(nodeCount); + this.initialCreatedNodes = new Node[nodeCount]; + this.createdNodes = new Node[nodeCount]; + } + + protected LoopScope(LoopScope outer, int loopDepth, int loopIteration, int loopBeginOrderId, Node[] initialCreatedNodes, Deque<LoopScope> nextIterations, + Map<LoopExplosionState, LoopExplosionState> iterationStates) { + this.outer = outer; + this.loopDepth = loopDepth; + this.loopIteration = loopIteration; + this.nextIterations = nextIterations; + this.iterationStates = iterationStates; + this.loopBeginOrderId = loopBeginOrderId; + this.nodesToProcess = new BitSet(initialCreatedNodes.length); + this.initialCreatedNodes = initialCreatedNodes; + this.createdNodes = Arrays.copyOf(initialCreatedNodes, initialCreatedNodes.length); + } + + @Override + public String toString() { + return loopDepth + "," + loopIteration + (loopBeginOrderId == -1 ? "" : "#" + loopBeginOrderId); + } + } + + protected static class LoopExplosionState { + public final FrameState state; + public final MergeNode merge; + public final int hashCode; + + protected LoopExplosionState(FrameState state, MergeNode merge) { + this.state = state; + this.merge = merge; + + int h = 0; + for (ValueNode value : state.values()) { + if (value == null) { + h = h * 31 + 1234; + } else { + h = h * 31 + value.hashCode(); + } + } + this.hashCode = h; + } + + @Override + public boolean equals(Object obj) { + if (!(obj instanceof LoopExplosionState)) { + return false; + } + + FrameState otherState = ((LoopExplosionState) obj).state; + FrameState thisState = state; + assert thisState.outerFrameState() == otherState.outerFrameState(); + + Iterator<ValueNode> thisIter = thisState.values().iterator(); + Iterator<ValueNode> otherIter = otherState.values().iterator(); + while (thisIter.hasNext() && otherIter.hasNext()) { + ValueNode thisValue = thisIter.next(); + ValueNode otherValue = otherIter.next(); + if (thisValue != otherValue) { + return false; + } + } + return thisIter.hasNext() == otherIter.hasNext(); + } + + @Override + public int hashCode() { + return hashCode; + } + } + + public final void decode(StructuredGraph graph, EncodedGraph encodedGraph) { + MethodScope methodScope = new MethodScope(graph, null, encodedGraph, LoopExplosionKind.NONE); + decode(methodScope); + cleanupGraph(methodScope); + methodScope.graph.verify(); + } + + protected final void decode(MethodScope methodScope) { + LoopScope loopScope = new LoopScope(methodScope); + if (methodScope.isInlinedMethod()) { + methodScope.startNode = methodScope.graph.add(new StartNode()); + methodScope.startNode.setNext(makeStubNode(methodScope, loopScope, GraphEncoder.FIRST_NODE_ORDER_ID)); + loopScope.nodesToProcess.set(GraphEncoder.FIRST_NODE_ORDER_ID); + } else { + methodScope.startNode = methodScope.graph.start(); + registerNode(loopScope, GraphEncoder.START_NODE_ORDER_ID, methodScope.startNode, false, false); + loopScope.nodesToProcess.set(GraphEncoder.START_NODE_ORDER_ID); + } + + while (loopScope != null) { + while (!loopScope.nodesToProcess.isEmpty()) { + loopScope = processNextNode(methodScope, loopScope); + } + + if (loopScope.nextIterations != null && !loopScope.nextIterations.isEmpty()) { + /* Loop explosion: process the loop iteration. */ + assert loopScope.nextIterations.peekFirst().loopIteration == loopScope.loopIteration + 1; + loopScope = loopScope.nextIterations.removeFirst(); + } else { + loopScope = loopScope.outer; + } + } + + if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) { + cleanupGraph(methodScope); + Debug.dump(methodScope.graph, "Before loop detection"); + detectLoops(methodScope.graph, methodScope.startNode); + } + } + + protected LoopScope processNextNode(MethodScope methodScope, LoopScope loopScope) { + int nodeOrderId = loopScope.nodesToProcess.nextSetBit(0); + loopScope.nodesToProcess.clear(nodeOrderId); + + FixedNode node = (FixedNode) lookupNode(loopScope, nodeOrderId); + if (node.isDeleted()) { + return loopScope; + } + + LoopScope successorAddScope = loopScope; + boolean updatePredecessors = true; + if (node instanceof LoopExitNode) { + successorAddScope = loopScope.outer; + updatePredecessors = methodScope.loopExplosion == LoopExplosionKind.NONE; + } + + methodScope.reader.setByteIndex(methodScope.nodeStartOffsets[nodeOrderId]); + int typeId = methodScope.reader.getUVInt(); + assert node.getNodeClass() == methodScope.encodedGraph.getNodeClasses()[typeId]; + readProperties(methodScope, node); + makeSuccessorStubs(methodScope, successorAddScope, node, updatePredecessors); + makeInputNodes(methodScope, loopScope, node, true); + + LoopScope resultScope = loopScope; + if (node instanceof LoopBeginNode) { + if (methodScope.loopExplosion != LoopExplosionKind.NONE) { + handleLoopExplosionBegin(methodScope, loopScope, (LoopBeginNode) node); + } + + } else if (node instanceof LoopExitNode) { + if (methodScope.loopExplosion != LoopExplosionKind.NONE) { + handleLoopExplosionProxyNodes(methodScope, loopScope, (LoopExitNode) node, nodeOrderId); + } else { + handleProxyNodes(methodScope, loopScope); + } + + } else if (node instanceof AbstractEndNode) { + LoopScope phiInputScope = loopScope; + LoopScope phiNodeScope = loopScope; + + if (methodScope.loopExplosion != LoopExplosionKind.NONE && node instanceof LoopEndNode) { + node = handleLoopExplosionEnd(methodScope, loopScope, (LoopEndNode) node); + phiNodeScope = loopScope.nextIterations.getLast(); + } + + int mergeOrderId = methodScope.reader.getUVInt(); + AbstractMergeNode merge = (AbstractMergeNode) lookupNode(phiNodeScope, mergeOrderId); + if (merge == null) { + merge = (AbstractMergeNode) makeStubNode(methodScope, phiNodeScope, mergeOrderId); + + if (merge instanceof LoopBeginNode) { + assert phiNodeScope == phiInputScope && phiNodeScope == loopScope; + resultScope = new LoopScope(loopScope, loopScope.loopDepth + 1, 0, mergeOrderId, Arrays.copyOf(loopScope.createdNodes, loopScope.createdNodes.length), // + methodScope.loopExplosion != LoopExplosionKind.NONE ? new ArrayDeque<>() : null, // + methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE ? new HashMap<>() : null); + phiNodeScope = resultScope; + + registerNode(phiInputScope, mergeOrderId, null, true, true); + phiInputScope.nodesToProcess.clear(mergeOrderId); + phiNodeScope.nodesToProcess.set(mergeOrderId); + } + } + + handlePhiFunctions(methodScope, phiInputScope, phiNodeScope, (AbstractEndNode) node, merge); + + } else if (node instanceof Invoke) { + simplifyInvoke(methodScope, loopScope, nodeOrderId, (Invoke) node); + + } else if (node instanceof ReturnNode) { + methodScope.returnNodes.add((ReturnNode) node); + } else if (node instanceof UnwindNode) { + assert methodScope.unwindNode == null : "graph can have only one UnwindNode"; + methodScope.unwindNode = (UnwindNode) node; + + } else { + simplifyFixedNode(methodScope, loopScope, nodeOrderId, node); + } + + return resultScope; + } + + /** + * Hook for subclasses. + * + * @param methodScope The current method. + * @param loopScope The current loop. + * @param invokeOrderId The orderId of the method invocation node. + * @param invoke The invocation node. + */ + protected void simplifyInvoke(MethodScope methodScope, LoopScope loopScope, int invokeOrderId, Invoke invoke) { + } + + protected void handleLoopExplosionBegin(MethodScope methodScope, LoopScope loopScope, LoopBeginNode loopBegin) { + checkLoopExplosionIteration(methodScope, loopScope); + + List<EndNode> predecessors = loopBegin.forwardEnds().snapshot(); + FixedNode successor = loopBegin.next(); + FrameState frameState = loopBegin.stateAfter(); + + if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) { + LoopExplosionState queryState = new LoopExplosionState(frameState, null); + LoopExplosionState existingState = loopScope.iterationStates.get(queryState); + if (existingState != null) { + loopBegin.replaceAtUsages(existingState.merge); + loopBegin.safeDelete(); + successor.safeDelete(); + for (EndNode predecessor : predecessors) { + existingState.merge.addForwardEnd(predecessor); + } + return; + } + } + + MergeNode merge = methodScope.graph.add(new MergeNode()); + loopBegin.replaceAtUsages(merge); + loopBegin.safeDelete(); + merge.setStateAfter(frameState); + merge.setNext(successor); + for (EndNode predecessor : predecessors) { + merge.addForwardEnd(predecessor); + } + + if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) { + LoopExplosionState explosionState = new LoopExplosionState(frameState, merge); + loopScope.iterationStates.put(explosionState, explosionState); + } + } + + /** + * Hook for subclasses. + * + * @param methodScope The current method. + * @param loopScope The current loop. + */ + protected void checkLoopExplosionIteration(MethodScope methodScope, LoopScope loopScope) { + throw shouldNotReachHere("when subclass uses loop explosion, it needs to implement this method"); + } + + protected FixedNode handleLoopExplosionEnd(MethodScope methodScope, LoopScope loopScope, LoopEndNode loopEnd) { + EndNode replacementNode = methodScope.graph.add(new EndNode()); + loopEnd.replaceAtPredecessor(replacementNode); + loopEnd.safeDelete(); + + assert methodScope.loopExplosion != LoopExplosionKind.NONE; + if (methodScope.loopExplosion != LoopExplosionKind.FULL_UNROLL || loopScope.nextIterations.isEmpty()) { + int nextIterationNumber = loopScope.nextIterations.isEmpty() ? loopScope.loopIteration + 1 : loopScope.nextIterations.getLast().loopIteration + 1; + LoopScope nextIterationScope = new LoopScope(loopScope.outer, loopScope.loopDepth, nextIterationNumber, loopScope.loopBeginOrderId, loopScope.initialCreatedNodes, + loopScope.nextIterations, loopScope.iterationStates); + loopScope.nextIterations.addLast(nextIterationScope); + registerNode(nextIterationScope, loopScope.loopBeginOrderId, null, true, true); + makeStubNode(methodScope, nextIterationScope, loopScope.loopBeginOrderId); + } + return replacementNode; + } + + /** + * Hook for subclasses. + * + * @param methodScope The current method. + * @param loopScope The current loop. + * @param nodeOrderId The orderId of the node. + * @param node The node to be simplified. + */ + protected void simplifyFixedNode(MethodScope methodScope, LoopScope loopScope, int nodeOrderId, FixedNode node) { + } + + protected void handleProxyNodes(MethodScope methodScope, LoopScope loopScope) { + int numProxies = methodScope.reader.getUVInt(); + for (int i = 0; i < numProxies; i++) { + int proxyOrderId = methodScope.reader.getUVInt(); + ProxyNode proxy = (ProxyNode) ensureNodeCreated(methodScope, loopScope, proxyOrderId); + /* + * The ProxyNode transports a value from the loop to the outer scope. We therefore + * register it in the outer scope. + */ + registerNode(loopScope.outer, proxyOrderId, proxy, false, false); + } + } + + protected void handleLoopExplosionProxyNodes(MethodScope methodScope, LoopScope loopScope, LoopExitNode loopExit, int loopExitOrderId) { + BeginNode begin = methodScope.graph.add(new BeginNode()); + + FrameState loopExitState = loopExit.stateAfter(); + FixedNode loopExitSuccessor = loopExit.next(); + loopExit.replaceAtPredecessor(begin); + + /* + * In the original graph, the loop exit is not a merge node. Multiple exploded loop + * iterations now take the same loop exit, so we have to introduce a new merge node to + * handle the merge. + */ + MergeNode merge; + if (lookupNode(loopScope.outer, loopExitOrderId) == null) { + merge = methodScope.graph.add(new MergeNode()); + registerNode(loopScope.outer, loopExitOrderId, merge, false, false); + merge.setNext(loopExitSuccessor); + } else { + merge = (MergeNode) loopScope.outer.createdNodes[loopExitOrderId]; + } + + FrameState oldStateAfter = merge.stateAfter(); + merge.setStateAfter(loopExitState); + if (oldStateAfter != null) { + oldStateAfter.safeDelete(); + } + + EndNode end = methodScope.graph.add(new EndNode()); + begin.setNext(end); + merge.addForwardEnd(end); + + /* + * Possibly create phi nodes for the original proxy nodes that flow out of the loop. Note + * that we definitely do not need a proxy node itself anymore, since the loop was exploded + * and is no longer present. + */ + int numProxies = methodScope.reader.getUVInt(); + for (int i = 0; i < numProxies; i++) { + int proxyOrderId = methodScope.reader.getUVInt(); + ProxyNode proxy = (ProxyNode) ensureNodeCreated(methodScope, loopScope, proxyOrderId); + ValueNode phiInput = proxy.value(); + ValueNode replacement; + + ValueNode existing = (ValueNode) loopScope.outer.createdNodes[proxyOrderId]; + if (existing == null || existing == phiInput) { + /* + * We are at the first loop exit, or the proxy carries the same value for all exits. + * We do not need a phi node yet. + */ + registerNode(loopScope.outer, proxyOrderId, phiInput, true, false); + replacement = phiInput; + + } else if (!merge.isPhiAtMerge(existing)) { + /* Now we have two different values, so we need to create a phi node. */ + PhiNode phi = methodScope.graph.addWithoutUnique(new ValuePhiNode(proxy.stamp(), merge)); + /* Add the inputs from all previous exits. */ + for (int j = 0; j < merge.phiPredecessorCount() - 1; j++) { + phi.addInput(existing); + } + /* Add the input from this exit. */ + phi.addInput(phiInput); + registerNode(loopScope.outer, proxyOrderId, phi, true, false); + replacement = phi; + + } else { + /* Phi node has been created before, so just add the new input. */ + PhiNode phi = (PhiNode) existing; + phi.addInput(phiInput); + replacement = phi; + } + + methodScope.graph.replaceFloating(proxy, replacement); + } + + loopExit.safeDelete(); + assert loopExitSuccessor.predecessor() == null; + merge.getNodeClass().getSuccessorEdges().update(merge, null, loopExitSuccessor); + } + + protected void handlePhiFunctions(MethodScope methodScope, LoopScope phiInputScope, LoopScope phiNodeScope, AbstractEndNode end, AbstractMergeNode merge) { + + if (end instanceof LoopEndNode) { + /* + * Fix the loop end index and the number of loop ends. When we do canonicalization + * during decoding, we can end up with fewer ends than the encoded graph had. And the + * order of loop ends can be different. + */ + int numEnds = ((LoopBeginNode) merge).loopEnds().count(); + ((LoopBeginNode) merge).nextEndIndex = numEnds; + ((LoopEndNode) end).endIndex = numEnds - 1; + + } else { + if (merge.ends == null) { + merge.ends = new NodeInputList<>(merge); + } + merge.addForwardEnd((EndNode) end); + } + + /* + * We create most phi functions lazily. Canonicalization and simplification during decoding + * can lead to dead branches that are not decoded, so we might not need all phi functions + * that the original graph contained. Since we process all predecessors before actually + * processing the merge node, we have the final phi function when processing the merge node. + * The only exception are loop headers of non-exploded loops: since backward branches are + * not processed yet when processing the loop body, we need to create all phi functions + * upfront. + */ + boolean lazyPhi = !(merge instanceof LoopBeginNode) || methodScope.loopExplosion != LoopExplosionKind.NONE; + int numPhis = methodScope.reader.getUVInt(); + for (int i = 0; i < numPhis; i++) { + int phiInputOrderId = methodScope.reader.getUVInt(); + int phiNodeOrderId = methodScope.reader.getUVInt(); + + ValueNode phiInput = (ValueNode) ensureNodeCreated(methodScope, phiInputScope, phiInputOrderId); + + ValueNode existing = (ValueNode) lookupNode(phiNodeScope, phiNodeOrderId); + if (lazyPhi && (existing == null || existing == phiInput)) { + /* Phi function not yet necessary. */ + registerNode(phiNodeScope, phiNodeOrderId, phiInput, true, false); + + } else if (!merge.isPhiAtMerge(existing)) { + /* + * Phi function is necessary. Create it and fill it with existing inputs as well as + * the new input. + */ + registerNode(phiNodeScope, phiNodeOrderId, null, true, true); + PhiNode phi = (PhiNode) ensureNodeCreated(methodScope, phiNodeScope, phiNodeOrderId); + + phi.setMerge(merge); + for (int j = 0; j < merge.phiPredecessorCount() - 1; j++) { + phi.addInput(existing); + } + phi.addInput(phiInput); + + } else { + /* Phi node has been created before, so just add the new input. */ + PhiNode phi = (PhiNode) existing; + phi.addInput(phiInput); + } + } + } + + protected Node instantiateNode(MethodScope methodScope, int nodeOrderId) { + methodScope.reader.setByteIndex(methodScope.nodeStartOffsets[nodeOrderId]); + NodeClass<?> nodeClass = methodScope.encodedGraph.getNodeClasses()[methodScope.reader.getUVInt()]; + return nodeClass.allocateInstance(); + } + + protected void readProperties(MethodScope methodScope, Node node) { + Fields fields = node.getNodeClass().getData(); + for (int pos = 0; pos < fields.getCount(); pos++) { + if (fields.getType(pos).isPrimitive()) { + long primitive = methodScope.reader.getSV(); + fields.setRawPrimitive(node, pos, primitive); + } else { + int objectId = methodScope.reader.getUVInt(); + Object value = methodScope.encodedGraph.getObjects()[objectId]; + fields.set(node, pos, value); + } + } + } + + /** + * Process the input edges of a node. Input nodes that have not yet been created must be + * non-fixed nodes (because fixed nodes are processed in reverse postorder. Such non-fixed nodes + * are created on demand (recursively since they can themselves reference not yet created + * nodes). + */ + protected void makeInputNodes(MethodScope methodScope, LoopScope loopScope, Node node, boolean updateUsages) { + Edges edges = node.getNodeClass().getEdges(Edges.Type.Inputs); + for (int index = 0; index < edges.getDirectCount(); index++) { + if (skipEdge(node, edges, index, true, true)) { + continue; + } + int orderId = methodScope.reader.getUVInt(); + Node value = ensureNodeCreated(methodScope, loopScope, orderId); + Edges.initializeNode(node, edges.getOffsets(), index, value); + if (updateUsages && value != null && !value.isDeleted()) { + edges.update(node, null, value); + + } + } + for (int index = edges.getDirectCount(); index < edges.getCount(); index++) { + if (skipEdge(node, edges, index, false, true)) { + continue; + } + int size = methodScope.reader.getSVInt(); + if (size != -1) { + NodeList<Node> nodeList = new NodeInputList<>(node, size); + Edges.initializeList(node, edges.getOffsets(), index, nodeList); + for (int idx = 0; idx < size; idx++) { + int orderId = methodScope.reader.getUVInt(); + Node value = ensureNodeCreated(methodScope, loopScope, orderId); + nodeList.initialize(idx, value); + if (updateUsages && value != null && !value.isDeleted()) { + edges.update(node, null, value); + } + } + } + } + } + + protected Node ensureNodeCreated(MethodScope methodScope, LoopScope loopScope, int nodeOrderId) { + if (nodeOrderId == GraphEncoder.NULL_ORDER_ID) { + return null; + } + Node node = lookupNode(loopScope, nodeOrderId); + if (node != null) { + return node; + } + + long readerByteIndex = methodScope.reader.getByteIndex(); + node = instantiateNode(methodScope, nodeOrderId); + assert !(node instanceof FixedNode); + + /* Read the properties of the node. */ + readProperties(methodScope, node); + /* There must not be any successors to read, since it is a non-fixed node. */ + assert node.getNodeClass().getEdges(Edges.Type.Successors).getCount() == 0; + /* Read the inputs of the node, possibly creating them recursively. */ + makeInputNodes(methodScope, loopScope, node, false); + methodScope.reader.setByteIndex(readerByteIndex); + + if (node instanceof ProxyNode || node instanceof PhiNode) { + /* + * We need these nodes as they were in the original graph, without any canonicalization + * or value numbering. + */ + node = methodScope.graph.addWithoutUnique(node); + + } else { + /* Allow subclasses to canonicalize and intercept nodes. */ + node = handleFloatingNodeBeforeAdd(methodScope, loopScope, node); + if (!node.isAlive()) { + node = methodScope.graph.addOrUnique(node); + } + node = handleFloatingNodeAfterAdd(methodScope, loopScope, node); + } + registerNode(loopScope, nodeOrderId, node, false, false); + return node; + } + + /** + * Hook for subclasses to process a non-fixed node before it is added to the graph. + * + * @param methodScope The current method. + * @param loopScope The current loop. + * @param node The node to be canonicalized. + * @return The replacement for the node, or the node itself. + */ + protected Node handleFloatingNodeBeforeAdd(MethodScope methodScope, LoopScope loopScope, Node node) { + return node; + } + + /** + * Hook for subclasses to process a non-fixed node after it is added to the graph. + * + * @param methodScope The current method. + * @param loopScope The current loop. + * @param node The node to be canonicalized. + * @return The replacement for the node, or the node itself. + */ + protected Node handleFloatingNodeAfterAdd(MethodScope methodScope, LoopScope loopScope, Node node) { + return node; + } + + /** + * Process successor edges of a node. We create the successor nodes so that we can fill the + * successor list, but no properties or edges are loaded yet. That is done when the successor is + * on top of the worklist in {@link #processNextNode}. + */ + protected void makeSuccessorStubs(MethodScope methodScope, LoopScope loopScope, Node node, boolean updatePredecessors) { + Edges edges = node.getNodeClass().getEdges(Edges.Type.Successors); + for (int index = 0; index < edges.getDirectCount(); index++) { + if (skipEdge(node, edges, index, true, true)) { + continue; + } + int orderId = methodScope.reader.getUVInt(); + Node value = makeStubNode(methodScope, loopScope, orderId); + Edges.initializeNode(node, edges.getOffsets(), index, value); + if (updatePredecessors && value != null) { + edges.update(node, null, value); + } + } + for (int index = edges.getDirectCount(); index < edges.getCount(); index++) { + if (skipEdge(node, edges, index, false, true)) { + continue; + } + int size = methodScope.reader.getSVInt(); + if (size != -1) { + NodeList<Node> nodeList = new NodeSuccessorList<>(node, size); + Edges.initializeList(node, edges.getOffsets(), index, nodeList); + for (int idx = 0; idx < size; idx++) { + int orderId = methodScope.reader.getUVInt(); + Node value = makeStubNode(methodScope, loopScope, orderId); + nodeList.initialize(idx, value); + if (updatePredecessors && value != null) { + edges.update(node, null, value); + } + } + } + } + } + + protected FixedNode makeStubNode(MethodScope methodScope, LoopScope loopScope, int nodeOrderId) { + if (nodeOrderId == GraphEncoder.NULL_ORDER_ID) { + return null; + } + FixedNode node = (FixedNode) lookupNode(loopScope, nodeOrderId); + if (node != null) { + return node; + } + + long readerByteIndex = methodScope.reader.getByteIndex(); + node = (FixedNode) methodScope.graph.add(instantiateNode(methodScope, nodeOrderId)); + /* Properties and edges are not filled yet, the node remains uninitialized. */ + methodScope.reader.setByteIndex(readerByteIndex); + + registerNode(loopScope, nodeOrderId, node, false, false); + loopScope.nodesToProcess.set(nodeOrderId); + return node; + } + + /** + * Returns false for {@link Edges} that are not necessary in the encoded graph because they are + * reconstructed using other sources of information. + */ + protected static boolean skipEdge(Node node, Edges edges, int index, boolean direct, boolean decode) { + if (node instanceof PhiNode) { + /* The inputs of phi functions are filled manually when the end nodes are processed. */ + assert edges.type() == Edges.Type.Inputs; + if (direct) { + assert index == edges.getDirectCount() - 1 : "PhiNode has one direct input (the MergeNode)"; + } else { + assert index == edges.getCount() - 1 : "PhiNode has one variable size input (the values)"; + if (decode) { + /* The values must not be null, so initialize with an empty list. */ + Edges.initializeList(node, edges.getOffsets(), index, new NodeInputList<>(node)); + } + } + return true; + + } else if (node instanceof AbstractMergeNode && edges.type() == Edges.Type.Inputs && !direct) { + /* The ends of merge nodes are filled manually when the ends are processed. */ + assert index == edges.getCount() - 1 : "MergeNode has one variable size input (the ends)"; + assert Edges.getNodeList(node, edges.getOffsets(), index) != null : "Input list must have been already created"; + return true; + } + return false; + } + + protected Node lookupNode(LoopScope loopScope, int nodeOrderId) { + return loopScope.createdNodes[nodeOrderId]; + } + + protected void registerNode(LoopScope loopScope, int nodeOrderId, Node node, boolean allowOverwrite, boolean allowNull) { + assert node == null || node.isAlive(); + assert allowNull || node != null; + assert allowOverwrite || lookupNode(loopScope, nodeOrderId) == null; + loopScope.createdNodes[nodeOrderId] = node; + } + + /* + * The following methods are a literal copy from GraphBuilderPhase. + */ + + protected void detectLoops(StructuredGraph currentGraph, FixedNode startInstruction) { + NodeBitMap visited = currentGraph.createNodeBitMap(); + NodeBitMap active = currentGraph.createNodeBitMap(); + Deque<Node> stack = new ArrayDeque<>(); + stack.add(startInstruction); + visited.mark(startInstruction); + while (!stack.isEmpty()) { + Node next = stack.peek(); + assert next.isDeleted() || visited.isMarked(next); + if (next.isDeleted() || active.isMarked(next)) { + stack.pop(); + if (!next.isDeleted()) { + active.clear(next); + } + } else { + active.mark(next); + for (Node n : next.cfgSuccessors()) { + if (active.contains(n)) { + // Detected cycle. + assert n instanceof MergeNode; + assert next instanceof EndNode; + MergeNode merge = (MergeNode) n; + EndNode endNode = (EndNode) next; + merge.removeEnd(endNode); + FixedNode afterMerge = merge.next(); + if (!(afterMerge instanceof EndNode) || !(((EndNode) afterMerge).merge() instanceof LoopBeginNode)) { + FrameState stateAfter = merge.stateAfter(); + merge.setNext(null); + merge.setStateAfter(null); + LoopBeginNode newLoopBegin = appendLoopBegin(currentGraph, merge); + newLoopBegin.setNext(afterMerge); + newLoopBegin.setStateAfter(stateAfter); + } + LoopBeginNode loopBegin = (LoopBeginNode) ((EndNode) merge.next()).merge(); + LoopEndNode loopEnd = currentGraph.add(new LoopEndNode(loopBegin)); + endNode.replaceAndDelete(loopEnd); + } else if (visited.contains(n)) { + // Normal merge into a branch we are already exploring. + } else { + visited.mark(n); + stack.push(n); + } + } + } + } + + Debug.dump(currentGraph, "After loops detected"); + insertLoopEnds(currentGraph, startInstruction); + } + + private static LoopBeginNode appendLoopBegin(StructuredGraph currentGraph, FixedWithNextNode fixedWithNext) { + EndNode preLoopEnd = currentGraph.add(new EndNode()); + LoopBeginNode loopBegin = currentGraph.add(new LoopBeginNode()); + fixedWithNext.setNext(preLoopEnd); + // Add the single non-loop predecessor of the loop header. + loopBegin.addForwardEnd(preLoopEnd); + return loopBegin; + } + + private static void insertLoopEnds(StructuredGraph currentGraph, FixedNode startInstruction) { + NodeBitMap visited = currentGraph.createNodeBitMap(); + Deque<Node> stack = new ArrayDeque<>(); + stack.add(startInstruction); + visited.mark(startInstruction); + List<LoopBeginNode> loopBegins = new ArrayList<>(); + while (!stack.isEmpty()) { + Node next = stack.pop(); + assert visited.isMarked(next); + if (next instanceof LoopBeginNode) { + loopBegins.add((LoopBeginNode) next); + } + for (Node n : next.cfgSuccessors()) { + if (visited.contains(n)) { + // Nothing to do. + } else { + visited.mark(n); + stack.push(n); + } + } + } + + IdentityHashMap<LoopBeginNode, List<LoopBeginNode>> innerLoopsMap = new IdentityHashMap<>(); + for (int i = loopBegins.size() - 1; i >= 0; --i) { + LoopBeginNode loopBegin = loopBegins.get(i); + insertLoopExits(currentGraph, loopBegin, innerLoopsMap); + } + + // Remove degenerated merges with only one predecessor. + for (LoopBeginNode loopBegin : loopBegins) { + Node pred = loopBegin.forwardEnd().predecessor(); + if (pred instanceof MergeNode) { + MergeNode.removeMergeIfDegenerated((MergeNode) pred); + } + } + } + + private static void insertLoopExits(StructuredGraph currentGraph, LoopBeginNode loopBegin, IdentityHashMap<LoopBeginNode, List<LoopBeginNode>> innerLoopsMap) { + NodeBitMap visited = currentGraph.createNodeBitMap(); + Deque<Node> stack = new ArrayDeque<>(); + for (LoopEndNode loopEnd : loopBegin.loopEnds()) { + stack.push(loopEnd); + visited.mark(loopEnd); + } + + List<ControlSplitNode> controlSplits = new ArrayList<>(); + List<LoopBeginNode> innerLoopBegins = new ArrayList<>(); + + while (!stack.isEmpty()) { + Node current = stack.pop(); + if (current == loopBegin) { + continue; + } + for (Node pred : current.cfgPredecessors()) { + if (!visited.isMarked(pred)) { + visited.mark(pred); + if (pred instanceof LoopExitNode) { + // Inner loop + LoopExitNode loopExitNode = (LoopExitNode) pred; + LoopBeginNode innerLoopBegin = loopExitNode.loopBegin(); + if (!visited.isMarked(innerLoopBegin)) { + stack.push(innerLoopBegin); + visited.mark(innerLoopBegin); + innerLoopBegins.add(innerLoopBegin); + } + } else { + if (pred instanceof ControlSplitNode) { + ControlSplitNode controlSplitNode = (ControlSplitNode) pred; + controlSplits.add(controlSplitNode); + } + stack.push(pred); + } + } + } + } + + for (ControlSplitNode controlSplit : controlSplits) { + for (Node succ : controlSplit.cfgSuccessors()) { + if (!visited.isMarked(succ)) { + LoopExitNode loopExit = currentGraph.add(new LoopExitNode(loopBegin)); + FixedNode next = ((FixedWithNextNode) succ).next(); + next.replaceAtPredecessor(loopExit); + loopExit.setNext(next); + } + } + } + + for (LoopBeginNode inner : innerLoopBegins) { + addLoopExits(currentGraph, loopBegin, inner, innerLoopsMap, visited); + } + + innerLoopsMap.put(loopBegin, innerLoopBegins); + } + + private static void addLoopExits(StructuredGraph currentGraph, LoopBeginNode loopBegin, LoopBeginNode inner, IdentityHashMap<LoopBeginNode, List<LoopBeginNode>> innerLoopsMap, NodeBitMap visited) { + for (LoopExitNode exit : inner.loopExits()) { + if (!visited.isMarked(exit)) { + LoopExitNode newLoopExit = currentGraph.add(new LoopExitNode(loopBegin)); + FixedNode next = exit.next(); + next.replaceAtPredecessor(newLoopExit); + newLoopExit.setNext(next); + } + } + + for (LoopBeginNode innerInner : innerLoopsMap.get(inner)) { + addLoopExits(currentGraph, loopBegin, innerInner, innerLoopsMap, visited); + } + } + + protected void cleanupGraph(MethodScope methodScope) { + assert verifyEdges(methodScope); + + Debug.dump(methodScope.graph, "Before removing redundant merges"); + for (MergeNode mergeNode : methodScope.graph.getNodes(MergeNode.TYPE)) { + if (mergeNode.forwardEndCount() == 1) { + methodScope.graph.reduceTrivialMerge(mergeNode); + } + } + + Debug.dump(methodScope.graph, "Before removing redundant begins"); + for (Node node : methodScope.graph.getNodes()) { + if (node instanceof BeginNode || node instanceof KillingBeginNode) { + if (!(node.predecessor() instanceof ControlSplitNode) && node.hasNoUsages()) { + GraphUtil.unlinkFixedNode((AbstractBeginNode) node); + node.safeDelete(); + } + } + } + + Debug.dump(methodScope.graph, "Before removing unused non-fixed nodes"); + for (Node node : methodScope.graph.getNodes()) { + if (!(node instanceof FixedNode) && node.hasNoUsages()) { + GraphUtil.killCFG(node); + } + } + } + + protected boolean verifyEdges(MethodScope methodScope) { + for (Node node : methodScope.graph.getNodes()) { + assert node.isAlive(); + node.acceptInputs((n, i) -> { + assert i.isAlive(); + assert i.usages().contains(n); + }); + node.acceptSuccessors((n, s) -> { + assert s.isAlive(); + assert s.predecessor() == n; + }); + + for (Node usage : node.usages()) { + assert usage.isAlive(); + assert usage.inputs().contains(node); + } + if (node.predecessor() != null) { + assert node.predecessor().isAlive(); + assert node.predecessor().successors().contains(node); + } + } + return true; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/GraphEncoder.java Wed Apr 08 22:38:40 2015 -0700 @@ -0,0 +1,468 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.nodes; + +import java.util.*; + +import com.oracle.graal.compiler.common.*; +import com.oracle.graal.compiler.common.util.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.graph.iterators.*; +import com.oracle.graal.nodes.StructuredGraph.AllowAssumptions; + +/** + * Encodes a {@link StructuredGraph} to a compact byte[] array. All nodes of the graph and edges + * between the nodes are encoded. Primitive data fields of nodes are stored in the byte[] array. + * Object data fields of nodes are stored in a separate Object[] array. + * + * One encoder instance can be used to encode multiple graphs. This requires that {@link #prepare} + * is called for all graphs first, followed by one call to {@link #finishPrepare}. Then + * {@link #encode} can be called for all graphs. The {@link #getObjects() objects} and + * {@link #getNodeClasses() node classes} arrays do not change anymore after preparation. + * + * Multiple encoded graphs share the Object[] array, and elements of the Object[] array are + * de-duplicated using {@link Object#equals Object equality}. This uses the assumption and good + * coding practice that data objects are immutable if {@link Object#equals} is implemented. + * Unfortunately, this cannot be enforced. + * + * The Graal {@link NodeClass} does not have a unique id that allows class lookup from an id. + * Therefore, the encoded graph contains a {@link NodeClass}[] array for lookup, and type ids are + * encoding-local. + * + * The encoded graph has the following structure: First, all nodes and their edges are serialized. + * The start offset of every node is then known. The raw node data is followed by a + * "table of contents" that lists the start offset for every node. + * + * The beginning of that table of contents is the return value of {@link #encode} and stored in + * {@link EncodedGraph#getStartOffset()}. The order of nodes in the table of contents is the + * {@link NodeOrder#orderIds orderId} of a node. Note that the orderId is not the regular node id + * that every Graal graph node gets assigned. The orderId is computed and used just for encoding and + * decoding. The orderId of fixed nodes is assigned in reverse postorder. The decoder processes + * nodes using that order, which ensures that all predecessors of a node (including all + * {@link EndNode predecessors} of a {@link AbstractBeginNode block}) are decoded before the node. + * The order id of floating node does not matter during decoding, so floating nodes get order ids + * after all fixed nodes. The order id is used to encode edges between nodes + * + * Structure of an encoded node: + * + * <pre> + * struct Node { + * unsigned typeId + * signed[] properties + * unsigned[] successorOrderIds + * unsigned[] inputOrderIds + * } + * </pre> + * + * All numbers (unsigned and signed) are stored using a variable-length encoding as defined in + * {@link TypeReader} and {@link TypeWriter}. Especially orderIds are small, so the variable-length + * encoding is important to keep the encoding compact. + * + * The properties, successors, and inputs are written in the order as defined in + * {@link NodeClass#getData}, {@link NodeClass#getSuccessorEdges()}, and + * {@link NodeClass#getInputEdges()}. For variable-length successors and input lists, first the + * length is written and then the orderIds. There is a distinction between null lists (encoded as + * length -1) and empty lists (encoded as length 0). No reverse edges are written (predecessors, + * usages) since that information can be easily restored during decoding. + * + * Some nodes have additional information written after the properties, successors, and inputs: <li> + * <item>{@link AbstractEndNode}: the orderId of the merge node and then all {@link PhiNode phi + * mappings} from this end to the merge node are written. <item>{@link LoopExitNode}: the orderId of + * all {@link ProxyNode proxy nodes} of the loop exit is written.</li> + */ +public class GraphEncoder { + + /** The orderId that always represents {@code null}. */ + public static final int NULL_ORDER_ID = 0; + /** The orderId of the {@link StructuredGraph#start() start node} of the encoded graph. */ + public static final int START_NODE_ORDER_ID = 1; + /** The orderId of the first actual node after the {@link StructuredGraph#start() start node}. */ + public static final int FIRST_NODE_ORDER_ID = 2; + + /** + * Collects all non-primitive data referenced from nodes. The encoding uses an index into an + * array for decoding. Because of the variable-length encoding, it is beneficial that frequently + * used objects have the small indices. + */ + protected final FrequencyEncoder<Object> objects; + /** + * Collects all node classes referenced in graphs. This is necessary because {@link NodeClass} + * currently does not have a unique id. + */ + protected final FrequencyEncoder<NodeClass<?>> nodeClasses; + /** The writer for the encoded graphs. */ + protected final UnsafeArrayTypeWriter writer; + + /** The last snapshot of {@link #objects} that was retrieved. */ + protected Object[] objectsArray; + /** The last snapshot of {@link #nodeClasses} that was retrieved. */ + protected NodeClass<?>[] nodeClassesArray; + + /** + * Utility method that does everything necessary to encode a single graph. + */ + public static EncodedGraph encodeSingleGraph(StructuredGraph graph) { + GraphEncoder encoder = new GraphEncoder(); + encoder.prepare(graph); + encoder.finishPrepare(); + long startOffset = encoder.encode(graph); + return new EncodedGraph(encoder.getEncoding(), startOffset, encoder.getObjects(), encoder.getNodeClasses(), graph.getAssumptions(), graph.getInlinedMethods()); + } + + public GraphEncoder() { + objects = FrequencyEncoder.createEqualityEncoder(); + nodeClasses = FrequencyEncoder.createIdentityEncoder(); + writer = new UnsafeArrayTypeWriter(); + } + + /** + * Must be invoked before {@link #finishPrepare()} and {@link #encode}. + */ + public void prepare(StructuredGraph graph) { + for (Node node : graph.getNodes()) { + nodeClasses.addObject(node.getNodeClass()); + + NodeClass<?> nodeClass = node.getNodeClass(); + for (int i = 0; i < nodeClass.getData().getCount(); i++) { + if (!nodeClass.getData().getType(i).isPrimitive()) { + objects.addObject(nodeClass.getData().get(node, i)); + } + } + } + } + + public void finishPrepare() { + objectsArray = objects.encodeAll(new Object[objects.getLength()]); + nodeClassesArray = nodeClasses.encodeAll(new NodeClass[nodeClasses.getLength()]); + } + + public Object[] getObjects() { + return objectsArray; + } + + public NodeClass<?>[] getNodeClasses() { + return nodeClassesArray; + } + + /** + * Compresses a graph to a byte array. Multiple graphs can be compressed with the same + * {@link GraphEncoder}. + * + * @param graph The graph to encode + */ + public long encode(StructuredGraph graph) { + assert objectsArray != null && nodeClassesArray != null : "finishPrepare() must be called before encode()"; + + NodeOrder nodeOrder = new NodeOrder(graph); + int nodeCount = nodeOrder.nextOrderId; + assert nodeOrder.orderIds.get(graph.start()) == START_NODE_ORDER_ID; + assert nodeOrder.orderIds.get(graph.start().next()) == FIRST_NODE_ORDER_ID; + assert nodeCount == graph.getNodeCount() + 1; + + long[] nodeStartOffsets = new long[nodeCount]; + for (Map.Entry<Node, Integer> entry : nodeOrder.orderIds.entries()) { + Node node = entry.getKey(); + nodeStartOffsets[entry.getValue()] = writer.getBytesWritten(); + + /* Write out the type, properties, and edges. */ + NodeClass<?> nodeClass = node.getNodeClass(); + writer.putUV(nodeClasses.getIndex(nodeClass)); + writeProperties(node, nodeClass.getData()); + writeEdges(node, nodeClass.getEdges(Edges.Type.Successors), nodeOrder); + writeEdges(node, nodeClass.getEdges(Edges.Type.Inputs), nodeOrder); + + /* Special handling for some nodes that require additional information for decoding. */ + if (node instanceof AbstractEndNode) { + AbstractEndNode end = (AbstractEndNode) node; + AbstractMergeNode merge = end.merge(); + /* + * Write the orderId of the merge. The merge is not a successor in the Graal graph + * (only the merge has an input edge to the EndNode). + */ + writeOrderId(merge, nodeOrder); + + /* + * Write all phi mappings (the oderId of the phi input for this EndNode, and the + * orderId of the phi node. + */ + writer.putUV(merge.phis().count()); + for (PhiNode phi : merge.phis()) { + writeOrderId(phi.valueAt(end), nodeOrder); + writeOrderId(phi, nodeOrder); + } + + } else if (node instanceof LoopExitNode) { + LoopExitNode exit = (LoopExitNode) node; + /* Write all proxy nodes of the LoopExitNode. */ + writer.putUV(exit.proxies().count()); + for (ProxyNode proxy : exit.proxies()) { + writeOrderId(proxy, nodeOrder); + } + } + } + + /* Write out the table of contents with the start offset for all nodes. */ + long nodeTableStart = writer.getBytesWritten(); + writer.putUV(nodeCount); + for (int i = 0; i < nodeCount; i++) { + assert i == NULL_ORDER_ID || i == START_NODE_ORDER_ID || nodeStartOffsets[i] > 0; + writer.putUV(nodeTableStart - nodeStartOffsets[i]); + } + + /* Check that the decoding of the encode graph is the same as the input. */ + assert verifyEncoding(graph, new EncodedGraph(getEncoding(), nodeTableStart, getObjects(), getNodeClasses(), graph.getAssumptions(), graph.getInlinedMethods())); + + return nodeTableStart; + } + + public byte[] getEncoding() { + return writer.toArray(new byte[TypeConversion.asS4(writer.getBytesWritten())]); + } + + static class NodeOrder { + protected final NodeMap<Integer> orderIds; + protected int nextOrderId; + + public NodeOrder(StructuredGraph graph) { + this.orderIds = new NodeMap<>(graph); + this.nextOrderId = START_NODE_ORDER_ID; + + /* Order the fixed nodes of the graph in reverse postorder. */ + Deque<AbstractBeginNode> nodeQueue = new ArrayDeque<>(); + FixedNode current = graph.start(); + do { + add(current); + if (current instanceof InvokeWithExceptionNode) { + /* + * Special handling for invokes: the orderID of the invocation, the regular + * successor, and the exception edge must be consecutive. + */ + add(((InvokeWithExceptionNode) current).next()); + add(((InvokeWithExceptionNode) current).exceptionEdge()); + } + + if (current instanceof FixedWithNextNode) { + current = ((FixedWithNextNode) current).next; + } else { + if (current instanceof ControlSplitNode) { + for (Node successor : current.successors()) { + if (successor != null) { + nodeQueue.addFirst((AbstractBeginNode) successor); + } + } + } else if (current instanceof EndNode) { + AbstractMergeNode merge = ((AbstractEndNode) current).merge(); + boolean allForwardEndsVisited = true; + for (int i = 0; i < merge.forwardEndCount(); i++) { + if (orderIds.get(merge.forwardEndAt(i)) == null) { + allForwardEndsVisited = false; + break; + } + } + if (allForwardEndsVisited) { + nodeQueue.add(merge); + } + } + current = nodeQueue.pollFirst(); + } + } while (current != null); + + for (Node node : graph.getNodes()) { + assert (node instanceof FixedNode) == (orderIds.get(node) != null) : "all fixed nodes must be ordered"; + add(node); + } + } + + private void add(Node node) { + if (orderIds.get(node) == null) { + orderIds.set(node, nextOrderId); + nextOrderId++; + } + } + } + + protected void writeProperties(Node node, Fields fields) { + for (int idx = 0; idx < fields.getCount(); idx++) { + if (fields.getType(idx).isPrimitive()) { + long primitive = fields.getRawPrimitive(node, idx); + writer.putSV(primitive); + } else { + Object property = fields.get(node, idx); + writer.putUV(objects.getIndex(property)); + } + } + } + + protected void writeEdges(Node node, Edges edges, NodeOrder nodeOrder) { + for (int idx = 0; idx < edges.getDirectCount(); idx++) { + if (GraphDecoder.skipEdge(node, edges, idx, true, false)) { + /* Edge is not needed for decoding, so we must not write it. */ + continue; + } + Node edge = Edges.getNode(node, edges.getOffsets(), idx); + writeOrderId(edge, nodeOrder); + } + for (int idx = edges.getDirectCount(); idx < edges.getCount(); idx++) { + if (GraphDecoder.skipEdge(node, edges, idx, false, false)) { + /* Edge is not needed for decoding, so we must not write it. */ + continue; + } + NodeList<Node> edgeList = Edges.getNodeList(node, edges.getOffsets(), idx); + if (edgeList == null) { + writer.putSV(-1); + } else { + writer.putSV(edgeList.size()); + for (Node edge : edgeList) { + writeOrderId(edge, nodeOrder); + } + } + } + } + + protected void writeOrderId(Node node, NodeOrder nodeOrder) { + writer.putUV(node == null ? NULL_ORDER_ID : nodeOrder.orderIds.get(node)); + } + + /** + * Verification code that checks that the decoding of an encode graph is the same as the + * original graph. + */ + public static boolean verifyEncoding(StructuredGraph originalGraph, EncodedGraph encodedGraph) { + StructuredGraph decodedGraph = new StructuredGraph(originalGraph.method(), AllowAssumptions.YES); + GraphDecoder decoder = new GraphDecoder(); + decoder.decode(decodedGraph, encodedGraph); + + decodedGraph.verify(); + GraphComparison.verifyGraphsEqual(originalGraph, decodedGraph); + return true; + } +} + +class GraphComparison { + public static boolean verifyGraphsEqual(StructuredGraph expectedGraph, StructuredGraph actualGraph) { + NodeMap<Node> nodeMapping = new NodeMap<>(expectedGraph); + Deque<Pair<Node, Node>> workList = new ArrayDeque<>(); + + pushToWorklist(expectedGraph.start(), actualGraph.start(), nodeMapping, workList); + while (!workList.isEmpty()) { + Pair<Node, Node> pair = workList.pop(); + Node expectedNode = pair.first; + Node actualNode = pair.second; + assert expectedNode.getClass() == actualNode.getClass(); + + NodeClass<?> nodeClass = expectedNode.getNodeClass(); + assert nodeClass == actualNode.getNodeClass(); + + if (expectedNode instanceof MergeNode) { + /* The order of the ends can be different, so ignore them. */ + verifyNodesEqual(expectedNode.inputs(), actualNode.inputs(), nodeMapping, workList, true); + } else if (expectedNode instanceof PhiNode) { + /* The order of phi inputs can be different, so they are checked manually below. */ + } else { + verifyNodesEqual(expectedNode.inputs(), actualNode.inputs(), nodeMapping, workList, false); + } + verifyNodesEqual(expectedNode.successors(), actualNode.successors(), nodeMapping, workList, false); + + if (expectedNode instanceof LoopEndNode) { + LoopEndNode actualLoopEnd = (LoopEndNode) actualNode; + assert actualLoopEnd.loopBegin().loopEnds().snapshot().indexOf(actualLoopEnd) == actualLoopEnd.endIndex(); + } else { + for (int i = 0; i < nodeClass.getData().getCount(); i++) { + Object expectedProperty = nodeClass.getData().get(expectedNode, i); + Object actualProperty = nodeClass.getData().get(actualNode, i); + assert Objects.equals(expectedProperty, actualProperty); + } + } + + if (expectedNode instanceof EndNode) { + /* Visit the merge node, which is the one and only usage of the EndNode. */ + assert expectedNode.usages().count() == 1; + assert actualNode.usages().count() == 1; + verifyNodesEqual(expectedNode.usages(), actualNode.usages(), nodeMapping, workList, false); + } + + if (expectedNode instanceof AbstractEndNode) { + /* Visit the input values of the merge phi functions for this EndNode. */ + verifyPhis((AbstractEndNode) expectedNode, (AbstractEndNode) actualNode, nodeMapping, workList); + } + } + + for (Node expectedNode : expectedGraph.getNodes()) { + assert nodeMapping.get(expectedNode) != null || (expectedNode.hasNoUsages() && !(expectedNode instanceof FixedNode)) : "expectedNode"; + } + return true; + } + + protected static void verifyPhis(AbstractEndNode expectedEndNode, AbstractEndNode actualEndNode, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList) { + AbstractMergeNode expectedMergeNode = expectedEndNode.merge(); + AbstractMergeNode actualMergeNode = (AbstractMergeNode) nodeMapping.get(expectedMergeNode); + + Iterator<PhiNode> actualPhis = actualMergeNode.phis().iterator(); + for (PhiNode expectedPhi : expectedMergeNode.phis()) { + PhiNode actualPhi = actualPhis.next(); + verifyNodeEqual(expectedPhi, actualPhi, nodeMapping, workList, false); + + ValueNode expectedPhiInput = expectedPhi.valueAt(expectedEndNode); + ValueNode actualPhiInput = actualPhi.valueAt(actualEndNode); + verifyNodeEqual(expectedPhiInput, actualPhiInput, nodeMapping, workList, false); + } + assert !actualPhis.hasNext(); + } + + private static void verifyNodesEqual(NodeIterable<Node> expectedNodes, NodeIterable<Node> actualNodes, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList, boolean ignoreEndNode) { + Iterator<Node> actualIter = actualNodes.iterator(); + for (Node expectedNode : expectedNodes) { + verifyNodeEqual(expectedNode, actualIter.next(), nodeMapping, workList, ignoreEndNode); + } + assert !actualIter.hasNext(); + } + + protected static void verifyNodeEqual(Node expectedNode, Node actualNode, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList, boolean ignoreEndNode) { + assert expectedNode.getClass() == actualNode.getClass(); + if (ignoreEndNode && expectedNode instanceof EndNode) { + return; + } + + Node existing = nodeMapping.get(expectedNode); + if (existing != null) { + assert existing == actualNode; + } else { + pushToWorklist(expectedNode, actualNode, nodeMapping, workList); + } + } + + protected static void pushToWorklist(Node expectedNode, Node actualNode, NodeMap<Node> nodeMapping, Deque<Pair<Node, Node>> workList) { + nodeMapping.set(expectedNode, actualNode); + workList.push(new Pair<>(expectedNode, actualNode)); + } +} + +class Pair<F, S> { + public final F first; + public final S second; + + public Pair(F first, S second) { + this.first = first; + this.second = second; + } +}
--- a/graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/ConditionAnchoringTest.java Wed Apr 08 22:07:50 2015 -0700 +++ b/graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/ConditionAnchoringTest.java Wed Apr 08 22:38:40 2015 -0700 @@ -137,7 +137,7 @@ @Override protected GraphBuilderConfiguration editGraphBuilderConfiguration(GraphBuilderConfiguration conf) { // get UnsafeAccessImpl.unsafeGetInt intrinsified - TruffleGraphBuilderPlugins.registerUnsafeAccessImplPlugins(conf.getPlugins().getInvocationPlugins()); + TruffleGraphBuilderPlugins.registerUnsafeAccessImplPlugins(conf.getPlugins().getInvocationPlugins(), false); // get UnsafeAccess.getInt inlined conf.getPlugins().setInlineInvokePlugin(new InlineEverythingPlugin()); conf.getPlugins().setLoadFieldPlugin(new FoldLoadsPlugins(getMetaAccess(), getConstantReflection()));
--- a/graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/SimplePartialEvaluationTest.java Wed Apr 08 22:07:50 2015 -0700 +++ b/graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/SimplePartialEvaluationTest.java Wed Apr 08 22:38:40 2015 -0700 @@ -61,9 +61,9 @@ } catch (SourceStackTrace t) { // Expected verification error occurred. StackTraceElement[] trace = t.getStackTrace(); - Assert.assertEquals("com.oracle.truffle.api.nodes.RootNode.getFrameDescriptor(RootNode.java)", trace[0].toString()); - String secondString = trace[1].toString(); - Assert.assertEquals("com.oracle.graal.truffle.OptimizedCallTarget.callRoot(OptimizedCallTarget.java:" /* "259)" */, secondString.substring(0, secondString.length() - 4)); + Assert.assertTrue(trace[0].toString().startsWith("com.oracle.truffle.api.CompilerAsserts.neverPartOfCompilation(CompilerAsserts.java:")); + Assert.assertTrue(trace[1].toString().startsWith("com.oracle.graal.truffle.test.nodes.NeverPartOfCompilationTestNode.execute(NeverPartOfCompilationTestNode.java:")); + Assert.assertTrue(trace[2].toString().startsWith("com.oracle.graal.truffle.test.nodes.RootTestNode.execute(RootTestNode.java:")); } } @@ -75,6 +75,13 @@ } @Test + public void twoMergesLoopExplosion() { + FrameDescriptor fd = new FrameDescriptor(); + AbstractTestNode result = new AddTestNode(new TwoMergesExplodedLoopTestNode(5), new ConstantTestNode(37)); + assertPartialEvalEquals("constant42", new RootTestNode(fd, "nestedLoopExplosion", result)); + } + + @Test public void sequenceConstants() { FrameDescriptor fd = new FrameDescriptor(); AbstractTestNode result = new BlockTestNode(new AbstractTestNode[]{new ConstantTestNode(40), new ConstantTestNode(42)});
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/nodes/TwoMergesExplodedLoopTestNode.java Wed Apr 08 22:38:40 2015 -0700 @@ -0,0 +1,63 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.truffle.test.nodes; + +import com.oracle.truffle.api.*; +import com.oracle.truffle.api.frame.*; +import com.oracle.truffle.api.nodes.*; + +@NodeInfo +public class TwoMergesExplodedLoopTestNode extends AbstractTestNode { + + static class Flag { + boolean flag = true; + } + + private final int count; + + public TwoMergesExplodedLoopTestNode(int count) { + this.count = count; + } + + @ExplodeLoop(merge = false) + @Override + public int execute(VirtualFrame frame) { + Flag flag = new Flag(); + int result = 0; + int i = 0; + while (i < count) { + i++; + + CompilerAsserts.partialEvaluationConstant(result); + + if (flag.flag) { + result++; + continue; + } else { + result--; + continue; + } + } + return result; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/CachingPEGraphDecoder.java Wed Apr 08 22:38:40 2015 -0700 @@ -0,0 +1,85 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.truffle; + +import java.util.*; + +import com.oracle.graal.api.meta.*; +import com.oracle.graal.api.replacements.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.graphbuilderconf.*; +import com.oracle.graal.java.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.StructuredGraph.AllowAssumptions; +import com.oracle.graal.phases.common.*; +import com.oracle.graal.phases.tiers.*; +import com.oracle.graal.phases.util.*; + +/** + * A graph decoder that provides all necessary encoded graphs on-the-fly (by parsing the methods and + * encoding the graphs). + */ +public class CachingPEGraphDecoder extends PEGraphDecoder { + + private final Providers providers; + private final GraphBuilderConfiguration graphBuilderConfig; + private final AllowAssumptions allowAssumptions; + private final Map<ResolvedJavaMethod, EncodedGraph> graphCache; + + public CachingPEGraphDecoder(Providers providers, SnippetReflectionProvider snippetReflection, GraphBuilderConfiguration graphBuilderConfig, AllowAssumptions allowAssumptions) { + super(providers.getMetaAccess(), providers.getConstantReflection(), providers.getStampProvider(), snippetReflection); + + this.providers = providers; + this.graphBuilderConfig = graphBuilderConfig; + this.allowAssumptions = allowAssumptions; + this.graphCache = new HashMap<>(); + } + + private EncodedGraph createGraph(ResolvedJavaMethod method) { + StructuredGraph graph = new StructuredGraph(method, allowAssumptions); + try (Debug.Scope scope = Debug.scope("createGraph", graph)) { + + new GraphBuilderPhase.Instance(providers.getMetaAccess(), providers.getStampProvider(), snippetReflection, providers.getConstantReflection(), graphBuilderConfig, + TruffleCompilerImpl.Optimizations, null).apply(graph); + + PhaseContext context = new PhaseContext(providers); + new CanonicalizerPhase().apply(graph, context); + + EncodedGraph encodedGraph = GraphEncoder.encodeSingleGraph(graph); + graphCache.put(method, encodedGraph); + return encodedGraph; + + } catch (Throwable ex) { + throw Debug.handle(ex); + } + } + + @Override + protected EncodedGraph lookupEncodedGraph(ResolvedJavaMethod method) { + EncodedGraph result = graphCache.get(method); + if (result == null && method.hasBytecodes()) { + result = createGraph(method); + } + return result; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/PEGraphDecoder.java Wed Apr 08 22:38:40 2015 -0700 @@ -0,0 +1,624 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.truffle; + +import static com.oracle.graal.compiler.common.GraalInternalError.*; +import static com.oracle.graal.java.AbstractBytecodeParser.Options.*; + +import java.util.*; + +import com.oracle.graal.api.code.*; +import com.oracle.graal.api.meta.*; +import com.oracle.graal.api.replacements.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.graph.spi.*; +import com.oracle.graal.graphbuilderconf.*; +import com.oracle.graal.graphbuilderconf.InlineInvokePlugin.InlineInfo; +import com.oracle.graal.graphbuilderconf.InvocationPlugins.InvocationPluginReceiver; +import com.oracle.graal.java.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.CallTargetNode.InvokeKind; +import com.oracle.graal.nodes.extended.*; +import com.oracle.graal.nodes.java.*; +import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.util.*; +import com.oracle.graal.phases.common.inlining.*; + +/** + * A graph decoder that performs partial evaluation, i.e., that performs method inlining and + * canonicalization/simplification of nodes during decoding. + * + * Inlining and loop explosion are configured via the plugin mechanism also used by the + * {@link GraphBuilderPhase}. However, not all callback methods defined in + * {@link GraphBuilderContext} are available since decoding is more limited than graph building. + * + * The standard {@link Canonicalizable#canonical node canonicalization} interface is used to + * canonicalize nodes during decoding. Additionally, {@link IfNode branches} and + * {@link IntegerSwitchNode switches} with constant conditions are simplified. + */ +public abstract class PEGraphDecoder extends GraphDecoder { + + protected final MetaAccessProvider metaAccess; + protected final ConstantReflectionProvider constantReflection; + protected final StampProvider stampProvider; + protected final SnippetReflectionProvider snippetReflection; + + protected class PEMethodScope extends MethodScope { + protected final ResolvedJavaMethod method; + protected final Invoke invoke; + protected final int inliningDepth; + + protected final LoopExplosionPlugin loopExplosionPlugin; + protected final InvocationPlugins invocationPlugins; + protected final InlineInvokePlugin inlineInvokePlugin; + protected final ParameterPlugin parameterPlugin; + protected final ValueNode[] arguments; + + protected FrameState outerFrameState; + protected BytecodePosition bytecodePosition; + + protected PEMethodScope(StructuredGraph targetGraph, MethodScope caller, EncodedGraph encodedGraph, ResolvedJavaMethod method, Invoke invoke, int inliningDepth, + LoopExplosionPlugin loopExplosionPlugin, InvocationPlugins invocationPlugins, InlineInvokePlugin inlineInvokePlugin, ParameterPlugin parameterPlugin, ValueNode[] arguments) { + super(targetGraph, caller, encodedGraph, loopExplosionKind(method, loopExplosionPlugin)); + + this.method = method; + this.invoke = invoke; + this.inliningDepth = inliningDepth; + this.loopExplosionPlugin = loopExplosionPlugin; + this.invocationPlugins = invocationPlugins; + this.inlineInvokePlugin = inlineInvokePlugin; + this.parameterPlugin = parameterPlugin; + this.arguments = arguments; + } + } + + protected class PECanonicalizerTool implements CanonicalizerTool { + @Override + public MetaAccessProvider getMetaAccess() { + return metaAccess; + } + + @Override + public ConstantReflectionProvider getConstantReflection() { + return constantReflection; + } + + @Override + public boolean canonicalizeReads() { + return true; + } + + @Override + public boolean allUsagesAvailable() { + return false; + } + } + + protected class PENonAppendGraphBuilderContext implements GraphBuilderContext { + private final PEMethodScope methodScope; + + public PENonAppendGraphBuilderContext(PEMethodScope methodScope) { + this.methodScope = methodScope; + } + + @Override + public BailoutException bailout(String string) { + throw new BailoutException(string); + } + + @Override + public StampProvider getStampProvider() { + return stampProvider; + } + + @Override + public MetaAccessProvider getMetaAccess() { + return metaAccess; + } + + @Override + public ConstantReflectionProvider getConstantReflection() { + return constantReflection; + } + + @Override + public SnippetReflectionProvider getSnippetReflection() { + return snippetReflection; + } + + @Override + public StructuredGraph getGraph() { + return methodScope.graph; + } + + @Override + public int getDepth() { + return methodScope.inliningDepth; + } + + @Override + public Replacement getReplacement() { + return null; + } + + @Override + public <T extends ValueNode> T append(T value) { + throw unimplemented(); + } + + @Override + public <T extends ValueNode> T recursiveAppend(T value) { + throw unimplemented(); + } + + @Override + public void push(Kind kind, ValueNode value) { + throw unimplemented(); + } + + @Override + public void handleReplacedInvoke(InvokeKind invokeKind, ResolvedJavaMethod targetMethod, ValueNode[] args) { + throw unimplemented(); + } + + @Override + public FrameState createStateAfter() { + throw unimplemented(); + } + + @Override + public GraphBuilderContext getParent() { + throw unimplemented(); + } + + @Override + public ResolvedJavaMethod getMethod() { + throw unimplemented(); + } + + @Override + public int bci() { + throw unimplemented(); + } + + @Override + public InvokeKind getInvokeKind() { + throw unimplemented(); + } + + @Override + public JavaType getInvokeReturnType() { + throw unimplemented(); + } + } + + protected class PEAppendGraphBuilderContext extends PENonAppendGraphBuilderContext { + protected final Invoke invoke; + protected FixedWithNextNode lastInstr; + protected ValueNode pushedNode; + + public PEAppendGraphBuilderContext(PEMethodScope methodScope, Invoke invoke, FixedWithNextNode lastInstr) { + super(methodScope); + this.invoke = invoke; + this.lastInstr = lastInstr; + } + + @Override + public void push(Kind kind, ValueNode value) { + if (pushedNode != null) { + throw unimplemented("Only one push is supported"); + } + pushedNode = value; + } + + @Override + public FrameState createStateAfter() { + return invoke.stateAfter().duplicate(); + } + + @Override + public <T extends ValueNode> T append(T v) { + if (v.graph() != null) { + return v; + } + T added = getGraph().addOrUnique(v); + if (added == v) { + updateLastInstruction(v); + } + return added; + } + + @Override + public <T extends ValueNode> T recursiveAppend(T v) { + if (v.graph() != null) { + return v; + } + T added = getGraph().addOrUniqueWithInputs(v); + if (added == v) { + updateLastInstruction(v); + } + return added; + } + + private <T extends ValueNode> void updateLastInstruction(T v) { + if (v instanceof FixedNode) { + FixedNode fixedNode = (FixedNode) v; + lastInstr.setNext(fixedNode); + if (fixedNode instanceof FixedWithNextNode) { + FixedWithNextNode fixedWithNextNode = (FixedWithNextNode) fixedNode; + assert fixedWithNextNode.next() == null : "cannot append instruction to instruction which isn't end"; + lastInstr = fixedWithNextNode; + } else { + lastInstr = null; + } + } + } + } + + public PEGraphDecoder(MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection, StampProvider stampProvider, SnippetReflectionProvider snippetReflection) { + this.metaAccess = metaAccess; + this.constantReflection = constantReflection; + this.stampProvider = stampProvider; + this.snippetReflection = snippetReflection; + } + + protected static LoopExplosionKind loopExplosionKind(ResolvedJavaMethod method, LoopExplosionPlugin loopExplosionPlugin) { + if (loopExplosionPlugin == null) { + return LoopExplosionKind.NONE; + } else if (loopExplosionPlugin.shouldMergeExplosions(method)) { + return LoopExplosionKind.MERGE_EXPLODE; + } else if (loopExplosionPlugin.shouldExplodeLoops(method)) { + return LoopExplosionKind.FULL_EXPLODE; + } else { + return LoopExplosionKind.NONE; + } + } + + public void decode(StructuredGraph targetGraph, ResolvedJavaMethod method, LoopExplosionPlugin loopExplosionPlugin, InvocationPlugins invocationPlugins, InlineInvokePlugin inlineInvokePlugin, + ParameterPlugin parameterPlugin) { + PEMethodScope methodScope = new PEMethodScope(targetGraph, null, lookupEncodedGraph(method), method, null, 0, loopExplosionPlugin, invocationPlugins, inlineInvokePlugin, parameterPlugin, null); + decode(methodScope); + cleanupGraph(methodScope); + methodScope.graph.verify(); + } + + @Override + protected void cleanupGraph(MethodScope methodScope) { + GraphBuilderPhase.connectLoopEndToBegin(methodScope.graph); + super.cleanupGraph(methodScope); + } + + @Override + protected void checkLoopExplosionIteration(MethodScope s, LoopScope loopScope) { + PEMethodScope methodScope = (PEMethodScope) s; + + Debug.dump(methodScope.graph, "Loop iteration " + loopScope.loopIteration); + + if (loopScope.loopIteration > MaximumLoopExplosionCount.getValue()) { + String message = "too many loop explosion iterations - does the explosion not terminate for method " + methodScope.method + "?"; + if (FailedLoopExplosionIsFatal.getValue()) { + throw new RuntimeException(message); + } else { + throw new BailoutException(message); + } + } + } + + @Override + protected void simplifyInvoke(MethodScope s, LoopScope loopScope, int invokeOrderId, Invoke invoke) { + if (!(invoke.callTarget() instanceof MethodCallTargetNode)) { + return; + } + PEMethodScope methodScope = (PEMethodScope) s; + MethodCallTargetNode callTarget = (MethodCallTargetNode) invoke.callTarget(); + + // attempt to devirtualize the call + ResolvedJavaType contextType = (invoke.stateAfter() == null && invoke.stateDuring() == null) ? null : invoke.getContextType(); + ResolvedJavaMethod specialCallTarget = MethodCallTargetNode.findSpecialCallTarget(callTarget.invokeKind(), callTarget.receiver(), callTarget.targetMethod(), contextType); + if (specialCallTarget != null) { + callTarget.setTargetMethod(specialCallTarget); + callTarget.setInvokeKind(InvokeKind.Special); + } + + if (tryInvocationPlugin(methodScope, loopScope, invokeOrderId, invoke)) { + return; + } + if (tryInline(methodScope, loopScope, invokeOrderId, invoke)) { + return; + } + + if (methodScope.inlineInvokePlugin != null) { + methodScope.inlineInvokePlugin.notifyOfNoninlinedInvoke(new PENonAppendGraphBuilderContext(methodScope), callTarget.targetMethod(), invoke); + } + } + + protected boolean tryInvocationPlugin(PEMethodScope methodScope, LoopScope loopScope, int invokeOrderId, Invoke invoke) { + if (methodScope.invocationPlugins == null) { + return false; + } + + MethodCallTargetNode callTarget = (MethodCallTargetNode) invoke.callTarget(); + ResolvedJavaMethod targetMethod = callTarget.targetMethod(); + InvocationPlugin invocationPlugin = methodScope.invocationPlugins.lookupInvocation(targetMethod); + if (invocationPlugin == null) { + return false; + } + + ValueNode[] arguments = callTarget.arguments().toArray(new ValueNode[0]); + FixedWithNextNode invokePredecessor = (FixedWithNextNode) invoke.asNode().predecessor(); + FixedNode invokeNext = invoke.next(); + AbstractBeginNode invokeException = null; + if (invoke instanceof InvokeWithExceptionNode) { + invokeException = ((InvokeWithExceptionNode) invoke).exceptionEdge(); + } + + invoke.asNode().replaceAtPredecessor(null); + + PEAppendGraphBuilderContext graphBuilderContext = new PEAppendGraphBuilderContext(methodScope, invoke, invokePredecessor); + InvocationPluginReceiver invocationPluginReceiver = new InvocationPluginReceiver(graphBuilderContext); + if (InvocationPlugin.execute(graphBuilderContext, targetMethod, invocationPlugin, invocationPluginReceiver.init(targetMethod, arguments), arguments)) { + + if (graphBuilderContext.lastInstr != null) { + registerNode(loopScope, invokeOrderId, graphBuilderContext.pushedNode, true, true); + invoke.asNode().replaceAtUsages(graphBuilderContext.pushedNode); + } else { + assert graphBuilderContext.pushedNode == null : "Why push a node when the invoke does not return anyway?"; + invoke.asNode().replaceAtUsages(null); + } + + deleteInvoke(invoke); + if (invokeException != null) { + invokeException.safeDelete(); + } + + if (graphBuilderContext.lastInstr != null) { + graphBuilderContext.lastInstr.setNext(invokeNext); + } else { + invokeNext.replaceAtPredecessor(null); + invokeNext.safeDelete(); + } + return true; + + } else { + /* Restore original state: invoke is in Graph. */ + invokePredecessor.setNext(invoke.asNode()); + return false; + } + } + + protected boolean tryInline(PEMethodScope methodScope, LoopScope loopScope, int invokeOrderId, Invoke invoke) { + if (methodScope.inlineInvokePlugin == null || !invoke.getInvokeKind().isDirect()) { + return false; + } + + MethodCallTargetNode callTarget = (MethodCallTargetNode) invoke.callTarget(); + ResolvedJavaMethod targetMethod = callTarget.targetMethod(); + if (!targetMethod.canBeInlined()) { + return false; + } + + ValueNode[] arguments = callTarget.arguments().toArray(new ValueNode[0]); + GraphBuilderContext graphBuilderContext = new PENonAppendGraphBuilderContext(methodScope); + InlineInfo inlineInfo = methodScope.inlineInvokePlugin.getInlineInfo(graphBuilderContext, targetMethod, arguments, callTarget.returnType()); + if (inlineInfo == null) { + return false; + } + assert !inlineInfo.isIntrinsic && !inlineInfo.isReplacement : "not supported"; + + ResolvedJavaMethod inlineMethod = inlineInfo.methodToInline; + EncodedGraph graphToInline = lookupEncodedGraph(inlineMethod); + if (graphToInline == null) { + return false; + } + + int exceptionObjectOrderId = -1; + if (invoke instanceof InvokeWithExceptionNode) { + /* + * We need to have the regular next node (usually a KillingBeginNode) and the exception + * edge node (always an ExceptionObjectNode) fully decoded, because both can be changed + * or replaced as part of the inlining process. The GraphEncoder adds these two + * successors in a known order (first the regular next node, then the exception edge) + * that we can rely on here. + */ + assert ((InvokeWithExceptionNode) invoke).next().next() == null; + processNextNode(methodScope, loopScope); + assert ((InvokeWithExceptionNode) invoke).next().next() != null; + + assert ((InvokeWithExceptionNode) invoke).exceptionEdge().next() == null; + exceptionObjectOrderId = loopScope.nodesToProcess.nextSetBit(0); + processNextNode(methodScope, loopScope); + assert ((InvokeWithExceptionNode) invoke).exceptionEdge().next() != null; + } + + PEMethodScope inlineScope = new PEMethodScope(methodScope.graph, methodScope, graphToInline, inlineMethod, invoke, methodScope.inliningDepth + 1, methodScope.loopExplosionPlugin, + methodScope.invocationPlugins, methodScope.inlineInvokePlugin, null, arguments); + /* Do the actual inlining by decoding the inlineMethod */ + decode(inlineScope); + + ValueNode exceptionValue = null; + if (inlineScope.unwindNode != null) { + exceptionValue = inlineScope.unwindNode.exception(); + } + + FixedNode firstInlinedNode = inlineScope.startNode.next(); + /* The StartNode was only necessary as a placeholder during decoding. */ + inlineScope.startNode.safeDelete(); + + assert inlineScope.startNode.stateAfter() == null; + ValueNode returnValue = InliningUtil.finishInlining(invoke, methodScope.graph, firstInlinedNode, inlineScope.returnNodes, inlineScope.unwindNode, inlineScope.encodedGraph.getAssumptions(), + inlineScope.encodedGraph.getInlinedMethods(), null); + + /* + * Usage the handles that we have on the return value and the exception to update the + * orderId->Node table. + */ + registerNode(loopScope, invokeOrderId, returnValue, true, true); + if (invoke instanceof InvokeWithExceptionNode) { + registerNode(loopScope, exceptionObjectOrderId, exceptionValue, true, true); + } + deleteInvoke(invoke); + + methodScope.inlineInvokePlugin.postInline(inlineMethod); + return true; + } + + private static void deleteInvoke(Invoke invoke) { + /* + * Clean up unused nodes. We cannot just call killCFG on the invoke node because that can + * kill too much: nodes that are decoded later can use values that appear unused by now. + */ + FrameState frameState = invoke.stateAfter(); + invoke.asNode().safeDelete(); + invoke.callTarget().safeDelete(); + if (frameState != null && frameState.hasNoUsages()) { + frameState.safeDelete(); + } + } + + protected abstract EncodedGraph lookupEncodedGraph(ResolvedJavaMethod method); + + @Override + protected void simplifyFixedNode(MethodScope s, LoopScope loopScope, int nodeOrderId, FixedNode node) { + PEMethodScope methodScope = (PEMethodScope) s; + + if (node instanceof IfNode && ((IfNode) node).condition() instanceof LogicConstantNode) { + IfNode ifNode = (IfNode) node; + boolean condition = ((LogicConstantNode) ifNode.condition()).getValue(); + AbstractBeginNode survivingSuccessor = ifNode.getSuccessor(condition); + AbstractBeginNode deadSuccessor = ifNode.getSuccessor(!condition); + + methodScope.graph.removeSplit(ifNode, survivingSuccessor); + assert deadSuccessor.next() == null : "must not be parsed yet"; + deadSuccessor.safeDelete(); + + } else if (node instanceof IntegerSwitchNode && ((IntegerSwitchNode) node).value().isConstant()) { + IntegerSwitchNode switchNode = (IntegerSwitchNode) node; + int value = switchNode.value().asJavaConstant().asInt(); + AbstractBeginNode survivingSuccessor = switchNode.successorAtKey(value); + List<Node> allSuccessors = switchNode.successors().snapshot(); + + methodScope.graph.removeSplit(switchNode, survivingSuccessor); + for (Node successor : allSuccessors) { + if (successor != survivingSuccessor) { + assert ((AbstractBeginNode) successor).next() == null : "must not be parsed yet"; + successor.safeDelete(); + } + } + + } else if (node instanceof Canonicalizable) { + Node canonical = ((Canonicalizable) node).canonical(new PECanonicalizerTool()); + if (canonical == null) { + /* + * This is a possible return value of canonicalization. However, we might need to + * add additional usages later on for which we need a node. Therefore, we just do + * nothing and leave the node in place. + */ + } else if (canonical != node) { + if (!canonical.isAlive()) { + assert !canonical.isDeleted(); + canonical = methodScope.graph.addOrUniqueWithInputs(canonical); + if (canonical instanceof FixedWithNextNode) { + methodScope.graph.addBeforeFixed(node, (FixedWithNextNode) canonical); + } + } + GraphUtil.unlinkFixedNode((FixedWithNextNode) node); + node.replaceAtUsages(canonical); + node.safeDelete(); + assert lookupNode(loopScope, nodeOrderId) == node; + registerNode(loopScope, nodeOrderId, canonical, true, false); + } + } + } + + @Override + protected Node handleFloatingNodeBeforeAdd(MethodScope s, LoopScope loopScope, Node node) { + PEMethodScope methodScope = (PEMethodScope) s; + + if (node instanceof ParameterNode) { + if (methodScope.arguments != null) { + Node result = methodScope.arguments[((ParameterNode) node).index()]; + assert result != null; + return result; + + } else if (methodScope.parameterPlugin != null) { + GraphBuilderContext graphBuilderContext = new PENonAppendGraphBuilderContext(methodScope); + Node result = methodScope.parameterPlugin.interceptParameter(graphBuilderContext, ((ParameterNode) node).index(), ((ParameterNode) node).stamp()); + if (result != null) { + return result; + } + } + + } else if (node instanceof Canonicalizable) { + Node canonical = ((Canonicalizable) node).canonical(new PECanonicalizerTool()); + if (canonical == null) { + /* + * This is a possible return value of canonicalization. However, we might need to + * add additional usages later on for which we need a node. Therefore, we just do + * nothing and leave the node in place. + */ + } else if (canonical != node) { + if (!canonical.isAlive()) { + assert !canonical.isDeleted(); + canonical = methodScope.graph.addOrUniqueWithInputs(canonical); + } + assert node.hasNoUsages(); + // methodScope.graph.replaceFloating((FloatingNode) node, canonical); + return canonical; + } + } + return node; + } + + @Override + protected Node handleFloatingNodeAfterAdd(MethodScope s, LoopScope loopScope, Node node) { + PEMethodScope methodScope = (PEMethodScope) s; + + if (methodScope.isInlinedMethod()) { + if (node instanceof SimpleInfopointNode) { + methodScope.bytecodePosition = InliningUtil.processSimpleInfopoint(methodScope.invoke, (SimpleInfopointNode) node, methodScope.bytecodePosition); + return node; + + } else if (node instanceof FrameState) { + FrameState stateAtExceptionEdge = null; + if (methodScope.invoke instanceof InvokeWithExceptionNode) { + InvokeWithExceptionNode invokeWithException = ((InvokeWithExceptionNode) methodScope.invoke); + ExceptionObjectNode obj = (ExceptionObjectNode) invokeWithException.exceptionEdge(); + stateAtExceptionEdge = obj.stateAfter(); + } + if (methodScope.outerFrameState == null) { + FrameState stateAtReturn = methodScope.invoke.stateAfter(); + Kind invokeReturnKind = methodScope.invoke.asNode().getKind(); + methodScope.outerFrameState = stateAtReturn.duplicateModifiedDuringCall(methodScope.invoke.bci(), invokeReturnKind); + } + return InliningUtil.processFrameState((FrameState) node, methodScope.invoke, methodScope.method, stateAtExceptionEdge, methodScope.outerFrameState, true); + + } else if (node instanceof MonitorIdNode) { + InliningUtil.processMonitorId(methodScope.invoke, (MonitorIdNode) node); + return node; + } + } + + return node; + } +}
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/PartialEvaluator.java Wed Apr 08 22:07:50 2015 -0700 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/PartialEvaluator.java Wed Apr 08 22:38:40 2015 -0700 @@ -22,8 +22,11 @@ */ package com.oracle.graal.truffle; +import static com.oracle.graal.compiler.common.GraalOptions.*; +import static com.oracle.graal.java.AbstractBytecodeParser.Options.*; import static com.oracle.graal.truffle.TruffleCompilerOptions.*; +import java.lang.invoke.*; import java.util.*; import com.oracle.graal.api.meta.*; @@ -41,6 +44,7 @@ import com.oracle.graal.nodes.java.*; import com.oracle.graal.nodes.spi.*; import com.oracle.graal.nodes.virtual.*; +import com.oracle.graal.options.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.common.*; import com.oracle.graal.phases.common.inlining.*; @@ -52,6 +56,7 @@ import com.oracle.graal.truffle.nodes.frame.*; import com.oracle.graal.truffle.nodes.frame.NewFrameNode.VirtualOnlyInstanceNode; import com.oracle.graal.truffle.phases.*; +import com.oracle.graal.truffle.substitutions.*; import com.oracle.graal.virtual.phases.ea.*; import com.oracle.truffle.api.*; import com.oracle.truffle.api.CompilerDirectives.TruffleBoundary; @@ -62,6 +67,9 @@ */ public class PartialEvaluator { + @Option(help = "New partial evaluation on Graal graphs", type = OptionType.Expert)// + public static final StableOptionValue<Boolean> GraphPE = new StableOptionValue<>(true); + private final Providers providers; private final CanonicalizerPhase canonicalizer; private final SnippetReflectionProvider snippetReflection; @@ -156,17 +164,44 @@ private class PEInlineInvokePlugin implements InlineInvokePlugin { + private final boolean duringParsing; private Deque<TruffleInlining> inlining; private OptimizedDirectCallNode lastDirectCallNode; private final Replacements replacements; - public PEInlineInvokePlugin(TruffleInlining inlining, Replacements replacements) { + private final InvocationPlugins invocationPlugins; + private final LoopExplosionPlugin loopExplosionPlugin; + + public PEInlineInvokePlugin(TruffleInlining inlining, Replacements replacements, boolean duringParsing, InvocationPlugins invocationPlugins, LoopExplosionPlugin loopExplosionPlugin) { this.inlining = new ArrayDeque<>(); this.inlining.push(inlining); this.replacements = replacements; + this.duringParsing = duringParsing; + this.invocationPlugins = invocationPlugins; + this.loopExplosionPlugin = loopExplosionPlugin; + } + + private boolean hasMethodHandleArgument(GraphBuilderContext builder, ValueNode[] arguments) { + /* + * We want to process invokes that have a constant MethodHandle parameter. And the + * method must be statically bound, otherwise we do not have a single target method. + */ + for (ValueNode argument : arguments) { + if (argument.isConstant()) { + JavaConstant constant = argument.asJavaConstant(); + if (constant.getKind() == Kind.Object && builder.getSnippetReflection().asObject(MethodHandle.class, constant) != null) { + return true; + } + } + } + return false; } public InlineInfo getInlineInfo(GraphBuilderContext builder, ResolvedJavaMethod original, ValueNode[] arguments, JavaType returnType) { + if (duringParsing && (invocationPlugins.lookupInvocation(original) != null || loopExplosionPlugin.shouldExplodeLoops(original))) { + return null; + } + if (original.getAnnotation(TruffleBoundary.class) != null) { return null; } @@ -176,6 +211,9 @@ assert !builder.parsingReplacement(); if (TruffleCompilerOptions.TruffleFunctionInlining.getValue()) { if (original.equals(callSiteProxyMethod)) { + if (duringParsing) { + return null; + } ValueNode arg1 = arguments[0]; if (!arg1.isConstant()) { GraalInternalError.shouldNotReachHere("The direct call node does not resolve to a constant!"); @@ -187,6 +225,9 @@ lastDirectCallNode = directCallNode; } } else if (original.equals(callDirectMethod)) { + if (duringParsing) { + return null; + } TruffleInliningDecision decision = getDecision(inlining.peek(), lastDirectCallNode); lastDirectCallNode = null; if (decision != null && decision.isInline()) { @@ -196,6 +237,11 @@ } } } + + if (duringParsing && (!original.hasBytecodes() || original.getCode().length >= TrivialInliningSize.getValue() || builder.getDepth() >= InlineDuringParsingMaxDepth.getValue()) && + !hasMethodHandleArgument(builder, arguments)) { + return null; + } return new InlineInfo(original, false, false); } @@ -222,28 +268,73 @@ } - @SuppressWarnings("unused") - private void fastPartialEvaluation(OptimizedCallTarget callTarget, StructuredGraph graph, PhaseContext baseContext, HighTierContext tierContext) { + protected void doFastPE(OptimizedCallTarget callTarget, StructuredGraph graph) { GraphBuilderConfiguration newConfig = configForRoot.copy(); + InvocationPlugins invocationPlugins = newConfig.getPlugins().getInvocationPlugins(); + TruffleGraphBuilderPlugins.registerInvocationPlugins(providers.getMetaAccess(), invocationPlugins, false); + newConfig.setUseProfiling(false); Plugins plugins = newConfig.getPlugins(); plugins.setLoadFieldPlugin(new InterceptLoadFieldPlugin()); plugins.setParameterPlugin(new InterceptReceiverPlugin(callTarget)); callTarget.setInlining(new TruffleInlining(callTarget, new DefaultInliningPolicy())); - InlineInvokePlugin inlinePlugin = new PEInlineInvokePlugin(callTarget.getInlining(), providers.getReplacements()); + + InlineInvokePlugin inlinePlugin = new PEInlineInvokePlugin(callTarget.getInlining(), providers.getReplacements(), false, null, null); if (PrintTruffleExpansionHistogram.getValue()) { inlinePlugin = new HistogramInlineInvokePlugin(graph, inlinePlugin); } plugins.setInlineInvokePlugin(inlinePlugin); plugins.setLoopExplosionPlugin(new PELoopExplosionPlugin()); - InvocationPlugins invocationPlugins = newConfig.getPlugins().getInvocationPlugins(); new GraphBuilderPhase.Instance(providers.getMetaAccess(), providers.getStampProvider(), this.snippetReflection, providers.getConstantReflection(), newConfig, TruffleCompilerImpl.Optimizations, null).apply(graph); if (PrintTruffleExpansionHistogram.getValue()) { ((HistogramInlineInvokePlugin) inlinePlugin).print(callTarget, System.out); } + } + + protected void doGraphPE(OptimizedCallTarget callTarget, StructuredGraph graph) { + GraphBuilderConfiguration newConfig = configForRoot.copy(); + InvocationPlugins parsingInvocationPlugins = newConfig.getPlugins().getInvocationPlugins(); + TruffleGraphBuilderPlugins.registerInvocationPlugins(providers.getMetaAccess(), parsingInvocationPlugins, true); + + callTarget.setInlining(new TruffleInlining(callTarget, new DefaultInliningPolicy())); + + LoopExplosionPlugin loopExplosionPlugin = new PELoopExplosionPlugin(); + + newConfig.setUseProfiling(false); + Plugins plugins = newConfig.getPlugins(); + plugins.setLoadFieldPlugin(new InterceptLoadFieldPlugin()); + plugins.setInlineInvokePlugin(new PEInlineInvokePlugin(callTarget.getInlining(), providers.getReplacements(), true, parsingInvocationPlugins, loopExplosionPlugin)); + + CachingPEGraphDecoder decoder = new CachingPEGraphDecoder(providers, snippetReflection, newConfig, AllowAssumptions.from(graph.getAssumptions() != null)); + + ParameterPlugin parameterPlugin = new InterceptReceiverPlugin(callTarget); + + InvocationPlugins decodingInvocationPlugins = new InvocationPlugins(providers.getMetaAccess()); + TruffleGraphBuilderPlugins.registerInvocationPlugins(providers.getMetaAccess(), decodingInvocationPlugins, false); + InlineInvokePlugin decodingInlinePlugin = new PEInlineInvokePlugin(callTarget.getInlining(), providers.getReplacements(), false, decodingInvocationPlugins, loopExplosionPlugin); + if (PrintTruffleExpansionHistogram.getValue()) { + decodingInlinePlugin = new HistogramInlineInvokePlugin(graph, decodingInlinePlugin); + } + + decoder.decode(graph, graph.method(), loopExplosionPlugin, decodingInvocationPlugins, decodingInlinePlugin, parameterPlugin); + + if (PrintTruffleExpansionHistogram.getValue()) { + ((HistogramInlineInvokePlugin) decodingInlinePlugin).print(callTarget, System.out); + } + } + + @SuppressWarnings("unused") + private void fastPartialEvaluation(OptimizedCallTarget callTarget, StructuredGraph graph, PhaseContext baseContext, HighTierContext tierContext) { + if (GraphPE.getValue()) { + doGraphPE(callTarget, graph); + } else { + doFastPE(callTarget, graph); + } Debug.dump(graph, "After FastPE"); + graph.maybeCompress(); + // Perform deoptimize to guard conversion. new ConvertDeoptimizeToGuardPhase().apply(graph, tierContext); @@ -269,6 +360,8 @@ // recompute loop frequencies now that BranchProbabilities have had time to canonicalize ComputeLoopFrequenciesClosure.compute(graph); + graph.maybeCompress(); + if (TruffleCompilerOptions.TraceTrufflePerformanceWarnings.getValue()) { reportPerformanceWarnings(graph); }
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCompilerImpl.java Wed Apr 08 22:07:50 2015 -0700 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCompilerImpl.java Wed Apr 08 22:38:40 2015 -0700 @@ -37,7 +37,7 @@ import com.oracle.graal.debug.*; import com.oracle.graal.debug.Debug.Scope; import com.oracle.graal.graphbuilderconf.*; -import com.oracle.graal.graphbuilderconf.GraphBuilderConfiguration.*; +import com.oracle.graal.graphbuilderconf.GraphBuilderConfiguration.Plugins; import com.oracle.graal.java.*; import com.oracle.graal.lir.asm.*; import com.oracle.graal.lir.phases.*; @@ -49,7 +49,6 @@ import com.oracle.graal.printer.*; import com.oracle.graal.runtime.*; import com.oracle.graal.truffle.nodes.*; -import com.oracle.graal.truffle.substitutions.*; import com.oracle.truffle.api.*; import com.oracle.truffle.api.nodes.*; @@ -98,7 +97,6 @@ GraphBuilderPhase phase = (GraphBuilderPhase) backend.getSuites().getDefaultGraphBuilderSuite().findPhase(GraphBuilderPhase.class).previous(); InvocationPlugins invocationPlugins = new InvocationPlugins(phase.getGraphBuilderConfig().getPlugins().getInvocationPlugins()); Plugins plugins = new Plugins(invocationPlugins); - TruffleGraphBuilderPlugins.registerInvocationPlugins(providers.getMetaAccess(), invocationPlugins); this.config = GraphBuilderConfiguration.getDefault(plugins).withSkippedExceptionTypes(skippedExceptionTypes);
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/asserts/NeverPartOfCompilationNode.java Wed Apr 08 22:07:50 2015 -0700 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/asserts/NeverPartOfCompilationNode.java Wed Apr 08 22:38:40 2015 -0700 @@ -29,13 +29,13 @@ import com.oracle.graal.nodes.util.*; @NodeInfo -public final class NeverPartOfCompilationNode extends FixedWithNextNode implements IterableNodeType { +public final class NeverPartOfCompilationNode extends AbstractStateSplit implements IterableNodeType { public static final NodeClass<NeverPartOfCompilationNode> TYPE = NodeClass.create(NeverPartOfCompilationNode.class); protected final String message; - public NeverPartOfCompilationNode(String message) { - super(TYPE, StampFactory.forVoid()); + public NeverPartOfCompilationNode(String message, FrameState stateAfter) { + super(TYPE, StampFactory.forVoid(), stateAfter); this.message = message; }
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/substitutions/TruffleGraphBuilderPlugins.java Wed Apr 08 22:07:50 2015 -0700 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/substitutions/TruffleGraphBuilderPlugins.java Wed Apr 08 22:38:40 2015 -0700 @@ -27,7 +27,6 @@ import java.util.concurrent.*; import com.oracle.graal.api.meta.*; -import com.oracle.graal.compiler.common.*; import com.oracle.graal.compiler.common.calc.*; import com.oracle.graal.compiler.common.type.*; import com.oracle.graal.graph.*; @@ -50,24 +49,24 @@ * Provides {@link InvocationPlugin}s for Truffle classes. */ public class TruffleGraphBuilderPlugins { - public static void registerInvocationPlugins(MetaAccessProvider metaAccess, InvocationPlugins plugins) { + public static void registerInvocationPlugins(MetaAccessProvider metaAccess, InvocationPlugins plugins, boolean canDelayIntrinsification) { - registerOptimizedAssumptionPlugins(plugins); + registerOptimizedAssumptionPlugins(plugins, canDelayIntrinsification); registerExactMathPlugins(plugins); registerCompilerDirectivesPlugins(plugins); - registerCompilerAssertsPlugins(plugins); + registerCompilerAssertsPlugins(plugins, canDelayIntrinsification); registerOptimizedCallTargetPlugins(metaAccess, plugins); - registerUnsafeAccessImplPlugins(plugins); + registerUnsafeAccessImplPlugins(plugins, canDelayIntrinsification); if (TruffleCompilerOptions.TruffleUseFrameWithoutBoxing.getValue()) { - registerFrameWithoutBoxingPlugins(plugins); + registerFrameWithoutBoxingPlugins(plugins, canDelayIntrinsification); } else { - registerFrameWithBoxingPlugins(plugins); + registerFrameWithBoxingPlugins(plugins, canDelayIntrinsification); } } - public static void registerOptimizedAssumptionPlugins(InvocationPlugins plugins) { + public static void registerOptimizedAssumptionPlugins(InvocationPlugins plugins, boolean canDelayIntrinsification) { Registration r = new Registration(plugins, OptimizedAssumption.class); InvocationPlugin plugin = new InvocationPlugin() { public boolean apply(GraphBuilderContext b, ResolvedJavaMethod targetMethod, Receiver receiver) { @@ -89,10 +88,12 @@ b.add(new DeoptimizeNode(DeoptimizationAction.InvalidateRecompile, DeoptimizationReason.None)); } } + return true; + } else if (canDelayIntrinsification) { + return false; } else { throw b.bailout("assumption could not be reduced to a constant"); } - return true; } }; r.register1("isValid", Receiver.class, plugin); @@ -204,7 +205,7 @@ }); } - public static void registerCompilerAssertsPlugins(InvocationPlugins plugins) { + public static void registerCompilerAssertsPlugins(InvocationPlugins plugins, boolean canDelayIntrinsification) { Registration r = new Registration(plugins, CompilerAsserts.class); r.register1("partialEvaluationConstant", Object.class, new InvocationPlugin() { public boolean apply(GraphBuilderContext b, ResolvedJavaMethod targetMethod, Receiver receiver, ValueNode value) { @@ -215,6 +216,8 @@ } if (curValue.isConstant()) { return true; + } else if (canDelayIntrinsification) { + return false; } else { StringBuilder sb = new StringBuilder(); sb.append(curValue); @@ -235,10 +238,13 @@ public boolean apply(GraphBuilderContext b, ResolvedJavaMethod targetMethod, Receiver receiver, ValueNode message) { if (message.isConstant()) { String messageString = message.asConstant().toValueString(); - b.add(new NeverPartOfCompilationNode(messageString)); + b.add(new NeverPartOfCompilationNode(messageString, b.createStateAfter())); return true; + } else if (canDelayIntrinsification) { + return false; + } else { + throw b.bailout("message for never part of compilation is non-constant"); } - throw b.bailout("message for never part of compilation is non-constant"); } }); } @@ -260,22 +266,22 @@ }); } - public static void registerFrameWithoutBoxingPlugins(InvocationPlugins plugins) { + public static void registerFrameWithoutBoxingPlugins(InvocationPlugins plugins, boolean canDelayIntrinsification) { Registration r = new Registration(plugins, FrameWithoutBoxing.class); registerMaterialize(r); - registerUnsafeCast(r); + registerUnsafeCast(r, canDelayIntrinsification); registerUnsafeLoadStorePlugins(r, Kind.Int, Kind.Long, Kind.Float, Kind.Double, Kind.Object); } - public static void registerFrameWithBoxingPlugins(InvocationPlugins plugins) { + public static void registerFrameWithBoxingPlugins(InvocationPlugins plugins, boolean canDelayIntrinsification) { Registration r = new Registration(plugins, FrameWithBoxing.class); registerMaterialize(r); - registerUnsafeCast(r); + registerUnsafeCast(r, canDelayIntrinsification); } - public static void registerUnsafeAccessImplPlugins(InvocationPlugins plugins) { + public static void registerUnsafeAccessImplPlugins(InvocationPlugins plugins, boolean canDelayIntrinsification) { Registration r = new Registration(plugins, UnsafeAccessImpl.class); - registerUnsafeCast(r); + registerUnsafeCast(r, canDelayIntrinsification); registerUnsafeLoadStorePlugins(r, Kind.Boolean, Kind.Byte, Kind.Int, Kind.Short, Kind.Long, Kind.Float, Kind.Double, Kind.Object); } @@ -288,7 +294,7 @@ }); } - private static void registerUnsafeCast(Registration r) { + private static void registerUnsafeCast(Registration r, boolean canDelayIntrinsification) { r.register4("unsafeCast", Object.class, Class.class, boolean.class, boolean.class, new InvocationPlugin() { public boolean apply(GraphBuilderContext b, ResolvedJavaMethod targetMethod, Receiver receiver, ValueNode object, ValueNode clazz, ValueNode condition, ValueNode nonNull) { if (clazz.isConstant() && nonNull.isConstant()) { @@ -322,8 +328,11 @@ b.addPush(Kind.Object, new PiNode(object, piStamp, valueAnchorNode)); } return true; + } else if (canDelayIntrinsification) { + return false; + } else { + throw b.bailout("unsafeCast arguments could not reduce to a constant: " + clazz + ", " + nonNull); } - throw GraalInternalError.shouldNotReachHere("unsafeCast arguments could not reduce to a constant: " + clazz + ", " + nonNull); } }); } @@ -359,7 +368,7 @@ b.addPush(returnKind.getStackKind(), b.add(new UnsafeLoadNode(object, offset, returnKind, locationIdentity, compare))); return true; } - // TODO: should we throw GraalInternalError.shouldNotReachHere() here? + // TODO: should we throw b.bailout() here? return false; } } @@ -385,7 +394,7 @@ b.add(new UnsafeStoreNode(object, offset, value, kind, locationIdentity, null)); return true; } - // TODO: should we throw GraalInternalError.shouldNotReachHere() here? + // TODO: should we throw b.bailout() here? return false; } }