Initial parser and writer for a light-weight IR.
Bug: b/225838009
Change-Id: I6c9b002488d62ccd26cf2fa1bda7dc2d699ad9fd
diff --git a/src/main/java/com/android/tools/r8/lightir/ByteArrayIterator.java b/src/main/java/com/android/tools/r8/lightir/ByteArrayIterator.java
new file mode 100644
index 0000000..c1f72dc
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/lightir/ByteArrayIterator.java
@@ -0,0 +1,41 @@
+// Copyright (c) 2022, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.lightir;
+
+import it.unimi.dsi.fastutil.bytes.ByteIterator;
+
+/** Simple implementation of an iterator over a primitive byte array. */
+public class ByteArrayIterator implements ByteIterator {
+
+ private final int size;
+ private final byte[] buffer;
+ private int index = 0;
+
+ public ByteArrayIterator(byte[] bytes) {
+ size = bytes.length;
+ buffer = bytes;
+ }
+
+ @Override
+ public boolean hasNext() {
+ return index < size;
+ }
+
+ @Override
+ public byte nextByte() {
+ return buffer[index++];
+ }
+
+ @Override
+ public Byte next() {
+ return nextByte();
+ }
+
+ @Override
+ public int skip(int i) {
+ int actual = index + i <= size ? i : size - index;
+ index += actual;
+ return actual;
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/lightir/ByteArrayWriter.java b/src/main/java/com/android/tools/r8/lightir/ByteArrayWriter.java
new file mode 100644
index 0000000..7636ed4
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/lightir/ByteArrayWriter.java
@@ -0,0 +1,23 @@
+// Copyright (c) 2022, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.lightir;
+
+import java.io.ByteArrayOutputStream;
+
+/** Simple implementation to construct a primitive byte array. */
+public class ByteArrayWriter implements ByteWriter {
+
+ // Backing is just the default capacity reallocating java byte array.
+ private final ByteArrayOutputStream buffer = new ByteArrayOutputStream();
+
+ @Override
+ public void put(int u1) {
+ assert ByteUtils.isU1(u1);
+ buffer.write(u1);
+ }
+
+ public byte[] toByteArray() {
+ return buffer.toByteArray();
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/lightir/ByteUtils.java b/src/main/java/com/android/tools/r8/lightir/ByteUtils.java
new file mode 100644
index 0000000..40a80d2
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/lightir/ByteUtils.java
@@ -0,0 +1,38 @@
+// Copyright (c) 2022, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.lightir;
+
+/** Simple utilities for byte encodings. */
+public class ByteUtils {
+
+ public static boolean isU1(int value) {
+ return 0 <= value && value <= 0xFF;
+ }
+
+ // Lossy truncation of an integer value to its lowest byte.
+ private static int truncateToU1(int value) {
+ return value & 0xFF;
+ }
+
+ public static int ensureU1(int value) {
+ assert isU1(value);
+ return truncateToU1(value);
+ }
+
+ public static int fromU1(byte value) {
+ return value & 0xFF;
+ }
+
+ public static int intEncodingSize(int value) {
+ return 4;
+ }
+
+ public static void writeEncodedInt(int value, ByteWriter writer) {
+ assert 4 == intEncodingSize(value);
+ writer.put(truncateToU1(value >> 24));
+ writer.put(truncateToU1(value >> 16));
+ writer.put(truncateToU1(value >> 8));
+ writer.put(truncateToU1(value));
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/lightir/ByteWriter.java b/src/main/java/com/android/tools/r8/lightir/ByteWriter.java
new file mode 100644
index 0000000..0a2a75e
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/lightir/ByteWriter.java
@@ -0,0 +1,11 @@
+// Copyright (c) 2022, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.lightir;
+
+/** Most primitive interface for providing consumer to the LIRWriter. */
+public interface ByteWriter {
+
+ /** Put a byte value, must represent an unsigned byte (int between 0 and 255). */
+ void put(int u1);
+}
diff --git a/src/main/java/com/android/tools/r8/lightir/LIRBasicInstructionCallback.java b/src/main/java/com/android/tools/r8/lightir/LIRBasicInstructionCallback.java
new file mode 100644
index 0000000..a08c036
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/lightir/LIRBasicInstructionCallback.java
@@ -0,0 +1,18 @@
+// Copyright (c) 2022, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.lightir;
+
+public interface LIRBasicInstructionCallback {
+
+ /**
+ * Most basic callback for interpreting LIR.
+ *
+ * @param opcode The opcode of the instruction (See {@code LIROpcodes} for values).
+ * @param operandsOffsetInBytes The offset into the byte stream at which the instruction's payload
+ * starts.
+ * @param operandsSizeInBytes The total size of the instruction's payload (excluding the opcode
+ * itself an any payload size encoding).
+ */
+ void onInstruction(int opcode, int operandsOffsetInBytes, int operandsSizeInBytes);
+}
diff --git a/src/main/java/com/android/tools/r8/lightir/LIRBuilder.java b/src/main/java/com/android/tools/r8/lightir/LIRBuilder.java
new file mode 100644
index 0000000..7ced9ef
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/lightir/LIRBuilder.java
@@ -0,0 +1,52 @@
+// Copyright (c) 2022, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.lightir;
+
+import com.android.tools.r8.graph.DexItem;
+import it.unimi.dsi.fastutil.objects.Reference2IntMap;
+import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap;
+
+public class LIRBuilder {
+
+ private final ByteArrayWriter byteWriter = new ByteArrayWriter();
+ private final LIRWriter writer = new LIRWriter(byteWriter);
+ private final Reference2IntMap<DexItem> constants;
+
+ public LIRBuilder() {
+ constants = new Reference2IntOpenHashMap<>();
+ }
+
+ private int getConstantIndex(DexItem item) {
+ int nextIndex = constants.size();
+ Integer oldIndex = constants.putIfAbsent(item, nextIndex);
+ return oldIndex != null ? oldIndex : nextIndex;
+ }
+
+ public LIRBuilder addNop() {
+ writer.writeOneByteInstruction(LIROpcodes.NOP);
+ return this;
+ }
+
+ public LIRBuilder addConstNull() {
+ writer.writeOneByteInstruction(LIROpcodes.ACONST_NULL);
+ return this;
+ }
+
+ public LIRBuilder addConstInt(int value) {
+ if (0 <= value && value <= 5) {
+ writer.writeOneByteInstruction(LIROpcodes.ICONST_0 + value);
+ } else {
+ writer.writeInstruction(LIROpcodes.ICONST, ByteUtils.intEncodingSize(value));
+ ByteUtils.writeEncodedInt(value, writer::writeOperand);
+ }
+ return this;
+ }
+
+ public LIRCode build() {
+ int constantsCount = constants.size();
+ DexItem[] constantTable = new DexItem[constantsCount];
+ constants.forEach((item, index) -> constantTable[index] = item);
+ return new LIRCode(constantTable, byteWriter.toByteArray());
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/lightir/LIRCode.java b/src/main/java/com/android/tools/r8/lightir/LIRCode.java
new file mode 100644
index 0000000..c91dbd9
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/lightir/LIRCode.java
@@ -0,0 +1,27 @@
+// Copyright (c) 2022, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.lightir;
+
+import com.android.tools.r8.graph.DexItem;
+
+public class LIRCode implements Iterable<LIRInstructionView> {
+
+ private final DexItem[] constants;
+ private final byte[] instructions;
+
+ public static LIRBuilder builder() {
+ return new LIRBuilder();
+ }
+
+ // Should be constructed using LIRBuilder.
+ LIRCode(DexItem[] constants, byte[] instructions) {
+ this.constants = constants;
+ this.instructions = instructions;
+ }
+
+ @Override
+ public LIRIterator iterator() {
+ return new LIRIterator(new ByteArrayIterator(instructions));
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/lightir/LIRInstructionView.java b/src/main/java/com/android/tools/r8/lightir/LIRInstructionView.java
new file mode 100644
index 0000000..59051e3
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/lightir/LIRInstructionView.java
@@ -0,0 +1,16 @@
+// Copyright (c) 2022, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.lightir;
+
+/**
+ * Abstract view of a LIR instruction.
+ *
+ * <p>The view should not be considered a representation of an instruction as the underlying data
+ * can change. The view callbacks allow interpreting the instruction at different levels of
+ * abstraction depending on need.
+ */
+public interface LIRInstructionView {
+
+ void accept(LIRBasicInstructionCallback eventCallback);
+}
diff --git a/src/main/java/com/android/tools/r8/lightir/LIRIterator.java b/src/main/java/com/android/tools/r8/lightir/LIRIterator.java
new file mode 100644
index 0000000..e05d521
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/lightir/LIRIterator.java
@@ -0,0 +1,61 @@
+// Copyright (c) 2022, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.lightir;
+
+import it.unimi.dsi.fastutil.bytes.ByteIterator;
+import java.util.Iterator;
+
+/**
+ * Basic iterator over the light IR.
+ *
+ * <p>This iterator is internally a zero-allocation parser with the "elements" as a view onto the
+ * current state.
+ */
+public class LIRIterator implements Iterator<LIRInstructionView>, LIRInstructionView {
+
+ private final ByteIterator iterator;
+
+ private int currentByteIndex = 0;
+ private int currentOpcode = -1;
+ private int currentOperandSize = 0;
+
+ public LIRIterator(ByteIterator iterator) {
+ this.iterator = iterator;
+ }
+
+ @Override
+ public boolean hasNext() {
+ return iterator.hasNext();
+ }
+
+ @Override
+ public LIRInstructionView next() {
+ currentOpcode = u1();
+ if (LIROpcodes.isOneByteInstruction(currentOpcode)) {
+ currentOperandSize = 0;
+ } else {
+ // Any instruction that is not a single byte has a two-byte header. The second byte is the
+ // size of the variable width operand payload.
+ currentOperandSize = u1();
+ skip(currentOperandSize);
+ }
+ return this;
+ }
+
+ @Override
+ public void accept(LIRBasicInstructionCallback eventCallback) {
+ int operandsOffset = currentByteIndex - currentOperandSize;
+ eventCallback.onInstruction(currentOpcode, operandsOffset, currentOperandSize);
+ }
+
+ private void skip(int i) {
+ currentByteIndex += i;
+ iterator.skip(i);
+ }
+
+ private int u1() {
+ ++currentByteIndex;
+ return ByteUtils.fromU1(iterator.nextByte());
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/lightir/LIROpcodes.java b/src/main/java/com/android/tools/r8/lightir/LIROpcodes.java
new file mode 100644
index 0000000..85cc9f1
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/lightir/LIROpcodes.java
@@ -0,0 +1,182 @@
+// Copyright (c) 2022, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.lightir;
+
+/**
+ * Constants related to LIR.
+ *
+ * <p>The constants generally follow the bytecode values as defined by the classfile format.
+ */
+public interface LIROpcodes {
+
+ static boolean isOneByteInstruction(int opcode) {
+ assert opcode >= NOP;
+ return opcode <= DCONST_1;
+ }
+
+ // Instructions maintaining the same opcode as defined in CF.
+ int NOP = 0;
+ int ACONST_NULL = 1;
+ int ICONST_M1 = 2;
+ int ICONST_0 = 3;
+ int ICONST_1 = 4;
+ int ICONST_2 = 5;
+ int ICONST_3 = 6;
+ int ICONST_4 = 7;
+ int ICONST_5 = 8;
+ int LCONST_0 = 9;
+ int LCONST_1 = 10;
+ int FCONST_0 = 11;
+ int FCONST_1 = 12;
+ int FCONST_2 = 13;
+ int DCONST_0 = 14;
+ int DCONST_1 = 15;
+ // int BIPUSH = 16;
+ // int SIPUSH = 17;
+ int LDC = 18;
+ // int ILOAD = 21;
+ // int LLOAD = 22;
+ // int FLOAD = 23;
+ // int DLOAD = 24;
+ // int ALOAD = 25;
+ int IALOAD = 46;
+ int LALOAD = 47;
+ int FALOAD = 48;
+ int DALOAD = 49;
+ int AALOAD = 50;
+ int BALOAD = 51;
+ int CALOAD = 52;
+ int SALOAD = 53;
+ // int ISTORE = 54;
+ // int LSTORE = 55;
+ // int FSTORE = 56;
+ // int DSTORE = 57;
+ // int ASTORE = 58;
+ int IASTORE = 79;
+ int LASTORE = 80;
+ int FASTORE = 81;
+ int DASTORE = 82;
+ int AASTORE = 83;
+ int BASTORE = 84;
+ int CASTORE = 85;
+ int SASTORE = 86;
+ // int POP = 87;
+ // int POP2 = 88;
+ // int DUP = 89;
+ // int DUP_X1 = 90;
+ // int DUP_X2 = 91;
+ // int DUP2 = 92;
+ // int DUP2_X1 = 93;
+ // int DUP2_X2 = 94;
+ // int SWAP = 95;
+ int IADD = 96;
+ int LADD = 97;
+ int FADD = 98;
+ int DADD = 99;
+ int ISUB = 100;
+ int LSUB = 101;
+ int FSUB = 102;
+ int DSUB = 103;
+ int IMUL = 104;
+ int LMUL = 105;
+ int FMUL = 106;
+ int DMUL = 107;
+ int IDIV = 108;
+ int LDIV = 109;
+ int FDIV = 110;
+ int DDIV = 111;
+ int IREM = 112;
+ int LREM = 113;
+ int FREM = 114;
+ int DREM = 115;
+ int INEG = 116;
+ int LNEG = 117;
+ int FNEG = 118;
+ int DNEG = 119;
+ int ISHL = 120;
+ int LSHL = 121;
+ int ISHR = 122;
+ int LSHR = 123;
+ int IUSHR = 124;
+ int LUSHR = 125;
+ int IAND = 126;
+ int LAND = 127;
+ int IOR = 128;
+ int LOR = 129;
+ int IXOR = 130;
+ int LXOR = 131;
+ // int IINC = 132;
+ int I2L = 133;
+ int I2F = 134;
+ int I2D = 135;
+ int L2I = 136;
+ int L2F = 137;
+ int L2D = 138;
+ int F2I = 139;
+ int F2L = 140;
+ int F2D = 141;
+ int D2I = 142;
+ int D2L = 143;
+ int D2F = 144;
+ int I2B = 145;
+ int I2C = 146;
+ int I2S = 147;
+ int LCMP = 148;
+ int FCMPL = 149;
+ int FCMPG = 150;
+ int DCMPL = 151;
+ int DCMPG = 152;
+ int IFEQ = 153;
+ int IFNE = 154;
+ int IFLT = 155;
+ int IFGE = 156;
+ int IFGT = 157;
+ int IFLE = 158;
+ int IF_ICMPEQ = 159;
+ int IF_ICMPNE = 160;
+ int IF_ICMPLT = 161;
+ int IF_ICMPGE = 162;
+ int IF_ICMPGT = 163;
+ int IF_ICMPLE = 164;
+ int IF_ACMPEQ = 165;
+ int IF_ACMPNE = 166;
+ int GOTO = 167;
+ // int JSR = 168;
+ // int RET = 169;
+ int TABLESWITCH = 170;
+ int LOOKUPSWITCH = 171;
+ int IRETURN = 172;
+ int LRETURN = 173;
+ int FRETURN = 174;
+ int DRETURN = 175;
+ int ARETURN = 176;
+ int RETURN = 177;
+ int GETSTATIC = 178;
+ int PUTSTATIC = 179;
+ int GETFIELD = 180;
+ int PUTFIELD = 181;
+ int INVOKEVIRTUAL = 182;
+ int INVOKESPECIAL = 183;
+ int INVOKESTATIC = 184;
+ int INVOKEINTERFACE = 185;
+ int INVOKEDYNAMIC = 186;
+ int NEW = 187;
+ int NEWARRAY = 188;
+ int ANEWARRAY = 189;
+ int ARRAYLENGTH = 190;
+ int ATHROW = 191;
+ int CHECKCAST = 192;
+ int INSTANCEOF = 193;
+ int MONITORENTER = 194;
+ int MONITOREXIT = 195;
+ int MULTIANEWARRAY = 197;
+ int IFNULL = 198;
+ int IFNONNULL = 199;
+
+ // Non-CF instructions.
+ int ICONST = 200;
+ int LCONST = 201;
+ int FCONST = 202;
+ int DCONST = 203;
+}
diff --git a/src/main/java/com/android/tools/r8/lightir/LIRWriter.java b/src/main/java/com/android/tools/r8/lightir/LIRWriter.java
new file mode 100644
index 0000000..074726d
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/lightir/LIRWriter.java
@@ -0,0 +1,39 @@
+// Copyright (c) 2022, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.lightir;
+
+/**
+ * Lowest level writer for constructing LIR encoded data.
+ *
+ * <p>This writer deals with just the instruction and operand encodings. For higher level structure,
+ * such as the constant pool, see LIRBuilder.
+ */
+public class LIRWriter {
+
+ private final ByteWriter writer;
+ private int pendingOperandBytes = 0;
+
+ public LIRWriter(ByteWriter writer) {
+ this.writer = writer;
+ }
+
+ public void writeOneByteInstruction(int opcode) {
+ assert LIROpcodes.isOneByteInstruction(opcode);
+ assert pendingOperandBytes == 0;
+ writer.put(ByteUtils.ensureU1(opcode));
+ }
+
+ public void writeInstruction(int opcode, int operandsSizeInBytes) {
+ assert pendingOperandBytes == 0;
+ writer.put(ByteUtils.ensureU1(opcode));
+ writer.put(ByteUtils.ensureU1(operandsSizeInBytes));
+ pendingOperandBytes = operandsSizeInBytes;
+ }
+
+ public void writeOperand(int u1) {
+ assert pendingOperandBytes > 0;
+ pendingOperandBytes--;
+ writer.put(ByteUtils.ensureU1(u1));
+ }
+}
diff --git a/src/test/java/com/android/tools/r8/lightir/LIRBasicCallbackTest.java b/src/test/java/com/android/tools/r8/lightir/LIRBasicCallbackTest.java
new file mode 100644
index 0000000..0602eb3
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/lightir/LIRBasicCallbackTest.java
@@ -0,0 +1,79 @@
+// Copyright (c) 2022, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.lightir;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertSame;
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.utils.IntBox;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class LIRBasicCallbackTest extends TestBase {
+
+ @Parameterized.Parameters(name = "{0}")
+ public static TestParametersCollection data() {
+ return getTestParameters().withNoneRuntime().build();
+ }
+
+ public LIRBasicCallbackTest(TestParameters parameters) {
+ parameters.assertNoneRuntime();
+ }
+
+ @Test
+ public void test() throws Exception {
+ LIRCode code = LIRCode.builder().addConstNull().addConstInt(42).build();
+
+ // State to keep track of position in the byte array as we don't expose this in the iterator.
+ IntBox offset = new IntBox(0);
+
+ LIRIterator it = code.iterator();
+
+ // The iterator and the elements are the same object providing a view on the byte stream.
+ assertTrue(it.hasNext());
+ LIRInstructionView next = it.next();
+ assertSame(it, next);
+
+ it.accept(
+ (int opcode, int operandOffset, int operandSize) -> {
+ int headerSize = 1;
+ assertEquals(LIROpcodes.ACONST_NULL, opcode);
+ assertEquals(offset.get() + headerSize, operandOffset);
+ assertEquals(0, operandSize);
+ offset.increment(headerSize + operandSize);
+ });
+
+ assertTrue(it.hasNext());
+ it.next();
+ it.accept(
+ (int opcode, int operandOffset, int operandSize) -> {
+ int headerSize = 2; // opcode + payload-size
+ assertEquals(LIROpcodes.ICONST, opcode);
+ assertEquals(offset.get() + headerSize, operandOffset);
+ assertEquals(4, operandSize);
+ offset.increment(headerSize + operandSize);
+ });
+ assertFalse(it.hasNext());
+
+ // The iterator can also be use in a normal java for-each loop.
+ // However, the item is not an actual item just a current view, so it can't be cached!
+ LIRInstructionView oldView = null;
+ for (LIRInstructionView view : code) {
+ if (oldView == null) {
+ oldView = view;
+ view.accept((opcode, ignore1, ignore2) -> assertEquals(LIROpcodes.ACONST_NULL, opcode));
+ } else {
+ assertSame(oldView, view);
+ view.accept((opcode, ignore1, ignore2) -> assertEquals(LIROpcodes.ICONST, opcode));
+ }
+ }
+ }
+}
