Reland "[LIR] Strategy for indirect phi references."
Bug: b/225838009
Change-Id: Idcccf97ea08e95dbe0c22691fd6a7e2a03c4c7ce
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
index c21f00e..0050541 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
@@ -65,7 +65,8 @@
import com.android.tools.r8.lightir.Lir2IRConverter;
import com.android.tools.r8.lightir.LirCode;
import com.android.tools.r8.lightir.LirStrategy;
-import com.android.tools.r8.lightir.LirStrategy.PhiInInstructionsStrategy;
+import com.android.tools.r8.lightir.LirStrategy.ExternalPhisStrategy;
+import com.android.tools.r8.lightir.PhiInInstructionsStrategy;
import com.android.tools.r8.naming.IdentifierNameStringMarker;
import com.android.tools.r8.optimize.argumentpropagation.ArgumentPropagatorIROptimizer;
import com.android.tools.r8.position.MethodPosition;
@@ -1055,12 +1056,18 @@
OptimizationFeedback feedback,
BytecodeMetadataProvider bytecodeMetadataProvider,
Timing timing) {
- LirStrategy<Value, Integer> strategy = new PhiInInstructionsStrategy();
- timing.begin("IR->LIR");
- LirCode<Integer> lirCode =
+ IRCode round1 = doRoundtripWithStrategy(code, new ExternalPhisStrategy(), "indirect phis");
+ IRCode round2 = doRoundtripWithStrategy(round1, new PhiInInstructionsStrategy(), "inline phis");
+ return round2;
+ }
+
+ private <EV, S extends LirStrategy<Value, EV>> IRCode doRoundtripWithStrategy(
+ IRCode code, S strategy, String name) {
+ timing.begin("IR->LIR (" + name + ")");
+ LirCode<EV> lirCode =
IR2LirConverter.translate(code, strategy.getEncodingStrategy(), appView.dexItemFactory());
timing.end();
- timing.begin("LIR->IR");
+ timing.begin("LIR->IR (" + name + ")");
IRCode irCode =
Lir2IRConverter.translate(
code.context(), lirCode, strategy.getDecodingStrategy(lirCode), appView);
diff --git a/src/main/java/com/android/tools/r8/lightir/ByteUtils.java b/src/main/java/com/android/tools/r8/lightir/ByteUtils.java
index f719f11..5d34483 100644
--- a/src/main/java/com/android/tools/r8/lightir/ByteUtils.java
+++ b/src/main/java/com/android/tools/r8/lightir/ByteUtils.java
@@ -51,6 +51,15 @@
return (value >= 0) && (value <= 0xFFFF);
}
+ private static int truncateToU2(int value) {
+ return value & 0xFFFF;
+ }
+
+ public static int ensureU2(int value) {
+ assert isU2(value);
+ return truncateToU2(value);
+ }
+
public static int unsetBitAtIndex(int value, int index) {
return value & ~(1 << (index - 1));
}
diff --git a/src/main/java/com/android/tools/r8/lightir/IR2LirConverter.java b/src/main/java/com/android/tools/r8/lightir/IR2LirConverter.java
index 21af715..ee53ceb 100644
--- a/src/main/java/com/android/tools/r8/lightir/IR2LirConverter.java
+++ b/src/main/java/com/android/tools/r8/lightir/IR2LirConverter.java
@@ -48,6 +48,11 @@
strategy.defineBlock(block, blockIndex);
}
+ private boolean recordPhi(Phi phi, int valueIndex) {
+ recordValue(phi, valueIndex);
+ return strategy.isPhiInlineInstruction();
+ }
+
private void recordValue(Value value, int valueIndex) {
EV encodedValue = strategy.defineValue(value, valueIndex);
if (value.hasLocalInfo()) {
@@ -69,16 +74,8 @@
BasicBlockIterator blockIt = irCode.listIterator();
while (blockIt.hasNext()) {
BasicBlock block = blockIt.next();
- if (block.hasPhis()) {
- // The block order of the predecessors may change, since the LIR does not encode the
- // direct links, the block order is used to determine predecessor order.
- int[] permutation = computePermutation(block.getPredecessors(), strategy::getBlockIndex);
- Value[] operands = new Value[block.getPredecessors().size()];
- for (Phi phi : block.getPhis()) {
- permuteOperands(phi.getOperands(), permutation, operands);
- builder.addPhi(phi.getType(), Arrays.asList(operands));
- currentValueIndex++;
- }
+ if (strategy.isPhiInlineInstruction()) {
+ currentValueIndex += computePhis(block);
}
if (block.hasCatchHandlers()) {
CatchHandlers<BasicBlock> handlers = block.getCatchHandlers();
@@ -112,6 +109,25 @@
}
assert builder.verifyCurrentValueIndex(currentValueIndex);
}
+ if (!strategy.isPhiInlineInstruction()) {
+ irCode.listIterator().forEachRemaining(this::computePhis);
+ }
+ }
+
+ private int computePhis(BasicBlock block) {
+ int valuesOffset = 0;
+ if (block.hasPhis()) {
+ // The block order of the predecessors may change, since the LIR does not encode the
+ // direct links, the block order is used to determine predecessor order.
+ int[] permutation = computePermutation(block.getPredecessors(), strategy::getBlockIndex);
+ Value[] operands = new Value[block.getPredecessors().size()];
+ for (Phi phi : block.getPhis()) {
+ permuteOperands(phi.getOperands(), permutation, operands);
+ builder.addPhi(phi.getType(), Arrays.asList(operands));
+ valuesOffset++;
+ }
+ }
+ return valuesOffset;
}
private void computeBlockAndValueTables() {
@@ -120,9 +136,10 @@
for (BasicBlock block : irCode.blocks) {
recordBlock(block, instructionIndex);
for (Phi phi : block.getPhis()) {
- recordValue(phi, valueIndex);
- valueIndex++;
- instructionIndex++;
+ if (recordPhi(phi, valueIndex)) {
+ valueIndex++;
+ instructionIndex++;
+ }
}
for (Instruction instruction : block.getInstructions()) {
if (instruction.hasOutValue()) {
diff --git a/src/main/java/com/android/tools/r8/lightir/Lir2IRConverter.java b/src/main/java/com/android/tools/r8/lightir/Lir2IRConverter.java
index b287683..e09e9f5 100644
--- a/src/main/java/com/android/tools/r8/lightir/Lir2IRConverter.java
+++ b/src/main/java/com/android/tools/r8/lightir/Lir2IRConverter.java
@@ -4,7 +4,6 @@
package com.android.tools.r8.lightir;
import com.android.tools.r8.graph.AppView;
-import com.android.tools.r8.graph.DebugLocalInfo;
import com.android.tools.r8.graph.DexField;
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.DexString;
@@ -58,6 +57,7 @@
AppView<?> appView) {
Parser<EV> parser = new Parser<>(lirCode, method.getReference(), appView, strategy);
parser.parseArguments(method);
+ parser.ensureDebugInfo();
lirCode.forEach(view -> view.accept(parser));
return parser.getIRCode(method);
}
@@ -157,6 +157,21 @@
advanceNextPositionEntry();
}
+ public void ensureDebugInfo() {
+ if (code.getDebugLocalInfoTable() == null) {
+ return;
+ }
+ code.getDebugLocalInfoTable()
+ .forEachLocalDefinition(
+ (encodedValue, localInfo) -> {
+ Value value = getValue(encodedValue);
+ if (!value.hasLocalInfo()) {
+ value.setLocalInfo(localInfo);
+ }
+ assert value.getLocalInfo() == localInfo;
+ });
+ }
+
// TODO(b/270398965): Replace LinkedList.
@SuppressWarnings("JdkObsolete")
public IRCode getIRCode(ProgramMethod method) {
@@ -194,7 +209,7 @@
}
public Value getValue(EV encodedValue) {
- return strategy.getValue(encodedValue);
+ return strategy.getValue(encodedValue, code.getStrategyInfo());
}
public List<Value> getValues(List<EV> indices) {
@@ -215,20 +230,34 @@
public Value getOutValueForNextInstruction(TypeElement type) {
int valueIndex = toInstructionIndexInIR(peekNextInstructionIndex());
- DebugLocalInfo localInfo = code.getDebugLocalInfo(valueIndex);
- return strategy.getValueDefinitionForInstructionIndex(valueIndex, type, localInfo);
+ return strategy.getValueDefinitionForInstructionIndex(
+ valueIndex, type, code::getDebugLocalInfo);
}
public Phi getPhiForNextInstructionAndAdvanceState(TypeElement type) {
- int valueIndex = toInstructionIndexInIR(peekNextInstructionIndex());
- DebugLocalInfo localInfo = code.getDebugLocalInfo(valueIndex);
- // TODO(b/225838009): The phi constructor implicitly adds to the block, so we need to ensure
- // the block. However, we must grab the index above. Find a way to clean this up so it is
- // uniform with instructions.
- advanceInstructionState();
- // Creating the phi implicitly adds it to currentBlock.
- return strategy.getPhiDefinitionForInstructionIndex(
- valueIndex, currentBlock, type, localInfo);
+ int instructionIndex = peekNextInstructionIndex();
+ int valueIndex = toInstructionIndexInIR(instructionIndex);
+ Phi phi =
+ strategy.getPhiDefinitionForInstructionIndex(
+ valueIndex,
+ blockIndex -> getBasicBlockOrEnsureCurrentBlock(blockIndex, instructionIndex),
+ type,
+ code::getDebugLocalInfo,
+ code.getStrategyInfo());
+ ensureCurrentPosition();
+ ++nextInstructionIndex;
+ return phi;
+ }
+
+ private BasicBlock getBasicBlockOrEnsureCurrentBlock(int index, int currentInstructionIndex) {
+ // If the index is at current or past it ensure the block.
+ if (index >= currentInstructionIndex) {
+ ensureCurrentBlock();
+ return currentBlock;
+ }
+ // Otherwise we assume the index is an exact block index for an existing block.
+ assert blocks.containsKey(index);
+ return getBasicBlock(index);
}
private void advanceInstructionState() {
@@ -262,8 +291,9 @@
// Arguments are not included in the "instructions" so this does not call "addInstruction"
// which would otherwise advance the state.
TypeElement typeElement = type.toTypeElement(appView);
- DebugLocalInfo localInfo = code.getDebugLocalInfo(index);
- Value dest = strategy.getValueDefinitionForInstructionIndex(index, typeElement, localInfo);
+ Value dest =
+ strategy.getValueDefinitionForInstructionIndex(
+ index, typeElement, code::getDebugLocalInfo);
Argument argument = new Argument(dest, index, type.isBooleanType());
assert currentBlock != null;
assert currentPosition.isSyntheticPosition();
diff --git a/src/main/java/com/android/tools/r8/lightir/LirBuilder.java b/src/main/java/com/android/tools/r8/lightir/LirBuilder.java
index b2fe3ba..fd4113a 100644
--- a/src/main/java/com/android/tools/r8/lightir/LirBuilder.java
+++ b/src/main/java/com/android/tools/r8/lightir/LirBuilder.java
@@ -433,6 +433,6 @@
instructionCount,
new TryCatchTable(tryCatchRanges),
debugTable,
- strategy.getSsaValueStrategy());
+ strategy.getStrategyInfo());
}
}
diff --git a/src/main/java/com/android/tools/r8/lightir/LirCode.java b/src/main/java/com/android/tools/r8/lightir/LirCode.java
index f62d9f6..3f84cdf 100644
--- a/src/main/java/com/android/tools/r8/lightir/LirCode.java
+++ b/src/main/java/com/android/tools/r8/lightir/LirCode.java
@@ -12,6 +12,7 @@
import com.android.tools.r8.ir.code.Position;
import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
import java.util.Map;
+import java.util.function.BiConsumer;
public class LirCode<EV> implements Iterable<LirInstructionView> {
@@ -48,9 +49,13 @@
this.valueToLocalMap = valueToLocalMap;
this.instructionToEndUseMap = instructionToEndUseMap;
}
+
+ public void forEachLocalDefinition(BiConsumer<EV, DebugLocalInfo> fn) {
+ valueToLocalMap.forEach(fn);
+ }
}
- private final LirSsaValueStrategy<EV> ssaValueStrategy;
+ private final LirStrategyInfo<EV> strategyInfo;
private final IRMetadata metadata;
@@ -89,7 +94,7 @@
int instructionCount,
TryCatchTable tryCatchTable,
DebugLocalInfoTable<EV> debugLocalInfoTable,
- LirSsaValueStrategy<EV> ssaValueStrategy) {
+ LirStrategyInfo<EV> strategyInfo) {
this.metadata = metadata;
this.constants = constants;
this.positionTable = positions;
@@ -98,11 +103,17 @@
this.instructionCount = instructionCount;
this.tryCatchTable = tryCatchTable;
this.debugLocalInfoTable = debugLocalInfoTable;
- this.ssaValueStrategy = ssaValueStrategy;
+ this.strategyInfo = strategyInfo;
}
public EV decodeValueIndex(int encodedValueIndex, int currentValueIndex) {
- return ssaValueStrategy.decodeValueIndex(encodedValueIndex, currentValueIndex);
+ return strategyInfo
+ .getReferenceStrategy()
+ .decodeValueIndex(encodedValueIndex, currentValueIndex);
+ }
+
+ public LirStrategyInfo<EV> getStrategyInfo() {
+ return strategyInfo;
}
public int getArgumentCount() {
@@ -137,7 +148,7 @@
return debugLocalInfoTable;
}
- public DebugLocalInfo getDebugLocalInfo(int valueIndex) {
+ public DebugLocalInfo getDebugLocalInfo(EV valueIndex) {
return debugLocalInfoTable == null ? null : debugLocalInfoTable.valueToLocalMap.get(valueIndex);
}
diff --git a/src/main/java/com/android/tools/r8/lightir/LirDecodingStrategy.java b/src/main/java/com/android/tools/r8/lightir/LirDecodingStrategy.java
index 1e25e3c..0b0a51d 100644
--- a/src/main/java/com/android/tools/r8/lightir/LirDecodingStrategy.java
+++ b/src/main/java/com/android/tools/r8/lightir/LirDecodingStrategy.java
@@ -7,15 +7,21 @@
import com.android.tools.r8.ir.analysis.type.TypeElement;
import com.android.tools.r8.ir.code.BasicBlock;
import com.android.tools.r8.ir.code.Phi;
+import java.util.function.Function;
+import java.util.function.IntFunction;
/** Abstraction for how to decode SSA values (and basic blocks) when reading LIR. */
public abstract class LirDecodingStrategy<V, EV> {
- public abstract V getValue(EV encodedValue);
+ public abstract V getValue(EV encodedValue, LirStrategyInfo<EV> strategyInfo);
public abstract V getValueDefinitionForInstructionIndex(
- int instructionIndex, TypeElement type, DebugLocalInfo localInfo);
+ int instructionIndex, TypeElement type, Function<EV, DebugLocalInfo> getLocalInfo);
public abstract Phi getPhiDefinitionForInstructionIndex(
- int instructionIndex, BasicBlock block, TypeElement type, DebugLocalInfo localInfo);
+ int valueIndex,
+ IntFunction<BasicBlock> getBlock,
+ TypeElement type,
+ Function<EV, DebugLocalInfo> getLocalInfo,
+ LirStrategyInfo<EV> strategyInfo);
}
diff --git a/src/main/java/com/android/tools/r8/lightir/LirEncodingStrategy.java b/src/main/java/com/android/tools/r8/lightir/LirEncodingStrategy.java
index 8bbba90..eb814d1 100644
--- a/src/main/java/com/android/tools/r8/lightir/LirEncodingStrategy.java
+++ b/src/main/java/com/android/tools/r8/lightir/LirEncodingStrategy.java
@@ -14,13 +14,17 @@
public abstract EV defineValue(V value, int index);
+ public abstract boolean isPhiInlineInstruction();
+
public abstract boolean verifyValueIndex(V value, int expectedIndex);
public abstract EV getEncodedValue(V value);
public int getEncodedValueIndexForReference(EV encodedValue, int referencingValueIndex) {
- return getSsaValueStrategy().encodeValueIndex(encodedValue, referencingValueIndex);
+ return getStrategyInfo()
+ .getReferenceStrategy()
+ .encodeValueIndex(encodedValue, referencingValueIndex);
}
- public abstract LirSsaValueStrategy<EV> getSsaValueStrategy();
+ public abstract LirStrategyInfo<EV> getStrategyInfo();
}
diff --git a/src/main/java/com/android/tools/r8/lightir/LirPrinter.java b/src/main/java/com/android/tools/r8/lightir/LirPrinter.java
index 20dfc30..f4a840b 100644
--- a/src/main/java/com/android/tools/r8/lightir/LirPrinter.java
+++ b/src/main/java/com/android/tools/r8/lightir/LirPrinter.java
@@ -53,7 +53,7 @@
}
private String fmtValueIndex(EV valueIndex) {
- return "v" + valueIndex;
+ return valueIndex.toString();
}
private String fmtInsnIndex(int instructionIndex) {
diff --git a/src/main/java/com/android/tools/r8/lightir/LirStrategy.java b/src/main/java/com/android/tools/r8/lightir/LirStrategy.java
index 70cda39..108586f 100644
--- a/src/main/java/com/android/tools/r8/lightir/LirStrategy.java
+++ b/src/main/java/com/android/tools/r8/lightir/LirStrategy.java
@@ -3,6 +3,8 @@
// BSD-style license that can be found in the LICENSE file.
package com.android.tools.r8.lightir;
+import com.android.tools.r8.errors.Unimplemented;
+import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.graph.DebugLocalInfo;
import com.android.tools.r8.ir.analysis.type.TypeElement;
import com.android.tools.r8.ir.code.BasicBlock;
@@ -11,6 +13,11 @@
import com.android.tools.r8.ir.code.Value;
import it.unimi.dsi.fastutil.objects.Reference2IntMap;
import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap;
+import java.util.ArrayList;
+import java.util.IdentityHashMap;
+import java.util.Map;
+import java.util.function.Function;
+import java.util.function.IntFunction;
/**
* Abstraction for encoding and decoding LIR values.
@@ -26,114 +33,326 @@
public abstract LirDecodingStrategy<V, EV> getDecodingStrategy(LirCode<EV> code);
- // Strategy that implements the encoding of phi values as instructions in the LIR instruction
- // stream.
- public static class PhiInInstructionsStrategy extends LirStrategy<Value, Integer> {
+ /**
+ * Encoding of a value with a phi-bit.
+ *
+ * <p>Due to the generic signature the encoding is boxed so this just adds some convenient
+ * predicates and formatting since it is boxed anyway.
+ *
+ * <p>JVM code attribute has length u2 (16-bit / max 65536). Thus, the number of basic blocks and
+ * phi count is also bounded by the same value. The encoding here is taken to be
+ *
+ * <ul>
+ * <li>1-bit for value/phi bit (sign bit / most significant bit),
+ * <li>15-bit phi index (the following most significant bits).
+ * <li>16-bit block index (the least significant bits).
+ * </ul>
+ *
+ * <p>TODO(b/225838009): Fix this encoding to support pathological block counts above 32k.
+ */
+ public static class PhiOrValue {
+ private final int value;
+
+ public static PhiOrValue forPhi(int blockIndex, int phiIndex) {
+ int sign = Integer.MIN_VALUE;
+ int block = ensure15bit(blockIndex) << 16;
+ int phi = ByteUtils.ensureU2(phiIndex);
+ int raw = sign | block | phi;
+ assert raw < 0;
+ return new PhiOrValue(raw);
+ }
+
+ private static int ensure15bit(int value) {
+ if (value >= (1 << 15)) {
+ // TODO(b/225838009): Support 16-bit values and inline this helper.
+ throw new Unimplemented("No support for more than 15-bit block index.");
+ }
+ return ByteUtils.ensureU2(value);
+ }
+
+ public static PhiOrValue forNonPhi(int index) {
+ assert index >= 0;
+ return new PhiOrValue(index);
+ }
+
+ private PhiOrValue(int value) {
+ this.value = value;
+ }
+
+ public boolean isPhi() {
+ return value < 0;
+ }
+
+ public boolean isNonPhi() {
+ return !isPhi();
+ }
+
+ public int getRawValue() {
+ return value;
+ }
+
+ public int getDecodedValue() {
+ assert isNonPhi();
+ return value;
+ }
+
+ public int getBlockIndex() {
+ assert isPhi();
+ return (value & ~Integer.MIN_VALUE) >> 16;
+ }
+
+ public int getPhiIndex() {
+ assert isPhi();
+ return value & 0xFFFF;
+ }
@Override
- public LirEncodingStrategy<Value, Integer> getEncodingStrategy() {
+ public String toString() {
+ if (isPhi()) {
+ return "phi(" + getBlockIndex() + "," + getPhiIndex() + ")";
+ }
+ return "v" + getDecodedValue();
+ }
+
+ @Override
+ public int hashCode() {
+ return value;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (obj == null) {
+ return false;
+ }
+ if (obj == this) {
+ return true;
+ }
+ return obj instanceof PhiOrValue && (value == ((PhiOrValue) obj).value);
+ }
+ }
+
+ public static class ExternalPhisStrategy extends LirStrategy<Value, PhiOrValue> {
+
+ @Override
+ public LirEncodingStrategy<Value, PhiOrValue> getEncodingStrategy() {
return new EncodingStrategy();
}
@Override
- public LirDecodingStrategy<Value, Integer> getDecodingStrategy(LirCode<Integer> code) {
+ public LirDecodingStrategy<Value, PhiOrValue> getDecodingStrategy(LirCode<PhiOrValue> code) {
return new DecodingStrategy(code);
}
- }
- private static class EncodingStrategy extends LirEncodingStrategy<Value, Integer> {
+ private static class StrategyInfo extends LirStrategyInfo<PhiOrValue> {
+ private static final StrategyInfo EMPTY = new StrategyInfo(new int[0]);
- // EV == Integer and its definition is equal to its shifted instruction index.
- // The conversion for EV to its int-valued reference is determined by the 'valueStrategy'.
+ private final int[] phiTable;
- private final LirSsaValueStrategy<Integer> valueStrategy = LirSsaValueStrategy.get();
- private final Reference2IntMap<Value> values = new Reference2IntOpenHashMap<>();
- private final Reference2IntMap<BasicBlock> blocks = new Reference2IntOpenHashMap<>();
-
- @Override
- public void defineBlock(BasicBlock block, int index) {
- assert !blocks.containsKey(block);
- blocks.put(block, index);
- }
-
- @Override
- public Integer defineValue(Value value, int index) {
- values.put(value, index);
- return index;
- }
-
- @Override
- public boolean verifyValueIndex(Value value, int expectedIndex) {
- assert expectedIndex == values.getInt(value);
- return true;
- }
-
- @Override
- public Integer getEncodedValue(Value value) {
- return values.getInt(value);
- }
-
- @Override
- public int getBlockIndex(BasicBlock block) {
- assert blocks.containsKey(block);
- return blocks.getInt(block);
- }
-
- @Override
- public LirSsaValueStrategy<Integer> getSsaValueStrategy() {
- return valueStrategy;
- }
- }
-
- private static class DecodingStrategy extends LirDecodingStrategy<Value, Integer> {
-
- private final Value[] values;
-
- DecodingStrategy(LirCode<Integer> code) {
- values = new Value[code.getArgumentCount() + code.getInstructionCount()];
- }
-
- @Override
- public Value getValue(Integer encodedValue) {
- int index = encodedValue;
- Value value = values[index];
- if (value == null) {
- value = new Value(index, TypeElement.getBottom(), null);
- values[index] = value;
+ public StrategyInfo(int[] phiTable) {
+ this.phiTable = phiTable;
}
- return value;
+
+ @Override
+ public LirSsaValueStrategy<PhiOrValue> getReferenceStrategy() {
+ return ReferenceStrategy.INSTANCE;
+ }
}
- @Override
- public Value getValueDefinitionForInstructionIndex(
- int index, TypeElement type, DebugLocalInfo localInfo) {
- Value value = values[index];
- if (value == null) {
- value = new Value(index, type, localInfo);
- values[index] = value;
- } else {
- value.setType(type);
- if (localInfo != null) {
- value.setLocalInfo(localInfo);
+ private static class EncodingStrategy extends LirEncodingStrategy<Value, PhiOrValue> {
+ private final Map<Value, PhiOrValue> values = new IdentityHashMap<>();
+ private final Reference2IntMap<BasicBlock> blocks = new Reference2IntOpenHashMap<>();
+ private final ArrayList<Integer> phiTable = new ArrayList<>();
+
+ @Override
+ public boolean isPhiInlineInstruction() {
+ return false;
+ }
+
+ @Override
+ public void defineBlock(BasicBlock block, int index) {
+ assert !blocks.containsKey(block);
+ blocks.put(block, index);
+ if (block.getPhis().isEmpty()) {
+ return;
}
+ int i = 0;
+ for (Phi phi : block.getPhis()) {
+ values.put(phi, PhiOrValue.forPhi(index, i++));
+ }
+ // Amend the phi table with the index of the basic block and the number of its phis.
+ phiTable.add(index);
+ phiTable.add(i);
}
- return value;
+
+ @Override
+ public PhiOrValue defineValue(Value value, int index) {
+ if (value.isPhi()) {
+ // Phis are defined as part of blocks.
+ PhiOrValue encodedValue = values.get(value);
+ assert encodedValue != null;
+ return encodedValue;
+ }
+ PhiOrValue encodedValue = PhiOrValue.forNonPhi(index);
+ values.put(value, encodedValue);
+ return encodedValue;
+ }
+
+ @Override
+ public boolean verifyValueIndex(Value value, int expectedIndex) {
+ PhiOrValue encodedValue = values.get(value);
+ assert encodedValue.isNonPhi();
+ assert expectedIndex == encodedValue.getDecodedValue();
+ return true;
+ }
+
+ @Override
+ public PhiOrValue getEncodedValue(Value value) {
+ return values.get(value);
+ }
+
+ @Override
+ public int getBlockIndex(BasicBlock block) {
+ assert blocks.containsKey(block);
+ return blocks.getInt(block);
+ }
+
+ @Override
+ public LirStrategyInfo<PhiOrValue> getStrategyInfo() {
+ if (phiTable.isEmpty()) {
+ return StrategyInfo.EMPTY;
+ }
+ int[] array = new int[phiTable.size()];
+ for (int i = 0; i < phiTable.size(); i++) {
+ array[i] = phiTable.get(i);
+ }
+ return new StrategyInfo(array);
+ }
}
- @Override
- public Phi getPhiDefinitionForInstructionIndex(
- int index, BasicBlock block, TypeElement type, DebugLocalInfo localInfo) {
- Phi phi = new Phi(index, block, type, localInfo, RegisterReadType.NORMAL);
- Value value = values[index];
- if (value != null) {
- // A fake ssa value has already been created, replace the users by the actual phi.
- // TODO(b/225838009): We could consider encoding the value type as a bit in the value index
- // and avoid the overhead of replacing users at phi-definition time.
- assert !value.isPhi();
- value.replaceUsers(phi);
+ private static class DecodingStrategy extends LirDecodingStrategy<Value, PhiOrValue> {
+
+ private final Value[] values;
+ private final int firstPhiValueIndex;
+
+ DecodingStrategy(LirCode<PhiOrValue> code) {
+ values = new Value[code.getArgumentCount() + code.getInstructionCount()];
+ int phiValueIndex = -1;
+ for (LirInstructionView view : code) {
+ if (view.getOpcode() == LirOpcodes.PHI) {
+ phiValueIndex = code.getArgumentCount() + view.getInstructionIndex();
+ break;
+ }
+ }
+ this.firstPhiValueIndex = phiValueIndex;
}
- values[index] = phi;
- return phi;
+
+ private int decode(PhiOrValue encodedValue, LirStrategyInfo<PhiOrValue> strategyInfo) {
+ if (encodedValue.isNonPhi()) {
+ return encodedValue.getDecodedValue();
+ }
+ StrategyInfo info = (StrategyInfo) strategyInfo;
+ int phiBlock = encodedValue.getBlockIndex();
+ int phiIndex = encodedValue.getPhiIndex();
+ assert firstPhiValueIndex != -1;
+ int index = firstPhiValueIndex;
+ for (int i = 0; i < info.phiTable.length; i++) {
+ int blockIndex = info.phiTable[i];
+ if (blockIndex == phiBlock) {
+ return index + phiIndex;
+ }
+ index += info.phiTable[++i];
+ }
+ throw new Unreachable("Unexpectedly fell off the end of the phi table");
+ }
+
+ @Override
+ public Value getValue(PhiOrValue encodedValue, LirStrategyInfo<PhiOrValue> strategyInfo) {
+ int index = decode(encodedValue, strategyInfo);
+ Value value = values[index];
+ if (value == null) {
+ value = new Value(index, TypeElement.getBottom(), null);
+ values[index] = value;
+ }
+ return value;
+ }
+
+ @Override
+ public Value getValueDefinitionForInstructionIndex(
+ int index, TypeElement type, Function<PhiOrValue, DebugLocalInfo> getLocalInfo) {
+ PhiOrValue encodedValue = new PhiOrValue(index);
+ assert encodedValue.isNonPhi();
+ DebugLocalInfo localInfo = getLocalInfo.apply(encodedValue);
+ Value value = values[index];
+ if (value == null) {
+ value = new Value(index, type, localInfo);
+ values[index] = value;
+ } else {
+ value.setType(type);
+ if (localInfo != null && !value.hasLocalInfo()) {
+ value.setLocalInfo(localInfo);
+ }
+ assert localInfo == value.getLocalInfo();
+ }
+ return value;
+ }
+
+ @Override
+ public Phi getPhiDefinitionForInstructionIndex(
+ int valueIndex,
+ IntFunction<BasicBlock> getBlock,
+ TypeElement type,
+ Function<PhiOrValue, DebugLocalInfo> getLocalInfo,
+ LirStrategyInfo<PhiOrValue> strategyInfo) {
+ PhiOrValue encodedValue = getEncodedPhiForAbsoluteValueIndex(valueIndex, strategyInfo);
+ BasicBlock block = getBlock.apply(encodedValue.getBlockIndex());
+ DebugLocalInfo localInfo = getLocalInfo.apply(encodedValue);
+ Phi phi = new Phi(valueIndex, block, type, localInfo, RegisterReadType.NORMAL);
+ Value value = values[valueIndex];
+ if (value != null) {
+ // A fake ssa value has already been created, replace the users by the actual phi.
+ // TODO(b/225838009): We could consider encoding the value phi-bit in the value index
+ // and avoid the overhead of replacing users at phi-definition time.
+ assert !value.isPhi();
+ value.replaceUsers(phi);
+ }
+ values[valueIndex] = phi;
+ return phi;
+ }
+
+ private PhiOrValue getEncodedPhiForAbsoluteValueIndex(
+ int phiValueIndex, LirStrategyInfo<PhiOrValue> strategyInfo) {
+ StrategyInfo info = (StrategyInfo) strategyInfo;
+ int currentPhiValueIndex = firstPhiValueIndex;
+ for (int i = 0; i < info.phiTable.length; i += 2) {
+ assert currentPhiValueIndex <= phiValueIndex;
+ int blockIndex = info.phiTable[i];
+ int phiCount = info.phiTable[i + 1];
+ assert phiCount > 0;
+ if (phiValueIndex < currentPhiValueIndex + phiCount) {
+ int phiOffsetInBlock = phiValueIndex - currentPhiValueIndex;
+ return PhiOrValue.forPhi(blockIndex, phiOffsetInBlock);
+ }
+ currentPhiValueIndex += phiCount;
+ }
+ throw new Unreachable("Unexpected fall off the end of the phi table");
+ }
+ }
+
+ // TODO(b/225838009): Consider still encoding the local value refs as small relative indexes.
+ private static class ReferenceStrategy extends LirSsaValueStrategy<PhiOrValue> {
+
+ private static final ReferenceStrategy INSTANCE = new ReferenceStrategy();
+
+ @Override
+ public int encodeValueIndex(PhiOrValue value, int currentValueIndex) {
+ return value.getRawValue();
+ }
+
+ @Override
+ public PhiOrValue decodeValueIndex(int encodedValueIndex, int currentValueIndex) {
+ return new PhiOrValue(encodedValueIndex);
+ }
}
}
+
}
diff --git a/src/main/java/com/android/tools/r8/lightir/LirStrategyInfo.java b/src/main/java/com/android/tools/r8/lightir/LirStrategyInfo.java
new file mode 100644
index 0000000..088786c
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/lightir/LirStrategyInfo.java
@@ -0,0 +1,9 @@
+// Copyright (c) 2023, 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 abstract class LirStrategyInfo<EV> {
+
+ public abstract LirSsaValueStrategy<EV> getReferenceStrategy();
+}
diff --git a/src/main/java/com/android/tools/r8/lightir/PhiInInstructionsStrategy.java b/src/main/java/com/android/tools/r8/lightir/PhiInInstructionsStrategy.java
new file mode 100644
index 0000000..0b0d537
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/lightir/PhiInInstructionsStrategy.java
@@ -0,0 +1,145 @@
+// Copyright (c) 2023, 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.DebugLocalInfo;
+import com.android.tools.r8.ir.analysis.type.TypeElement;
+import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.Phi;
+import com.android.tools.r8.ir.code.Phi.RegisterReadType;
+import com.android.tools.r8.ir.code.Value;
+import it.unimi.dsi.fastutil.objects.Reference2IntMap;
+import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap;
+import java.util.function.Function;
+import java.util.function.IntFunction;
+
+/** Strategy encoding phi values as instructions in the LIR instruction stream. */
+public class PhiInInstructionsStrategy extends LirStrategy<Value, Integer> {
+
+ @Override
+ public LirEncodingStrategy<Value, Integer> getEncodingStrategy() {
+ return new EncodingStrategy();
+ }
+
+ @Override
+ public LirDecodingStrategy<Value, Integer> getDecodingStrategy(LirCode<Integer> code) {
+ return new DecodingStrategy(code);
+ }
+
+ private static class EncodingStrategy extends LirEncodingStrategy<Value, Integer> {
+
+ // EV == Integer and its definition is equal to its shifted instruction index.
+ // The conversion for EV to its int-valued reference is determined by the 'valueStrategy'.
+
+ private final LirSsaValueStrategy<Integer> referenceStrategy = LirSsaValueStrategy.get();
+ private final Reference2IntMap<Value> values = new Reference2IntOpenHashMap<>();
+ private final Reference2IntMap<BasicBlock> blocks = new Reference2IntOpenHashMap<>();
+
+ @Override
+ public boolean isPhiInlineInstruction() {
+ return true;
+ }
+
+ @Override
+ public void defineBlock(BasicBlock block, int index) {
+ assert !blocks.containsKey(block);
+ blocks.put(block, index);
+ }
+
+ @Override
+ public Integer defineValue(Value value, int index) {
+ values.put(value, index);
+ return index;
+ }
+
+ @Override
+ public boolean verifyValueIndex(Value value, int expectedIndex) {
+ assert expectedIndex == values.getInt(value);
+ return true;
+ }
+
+ @Override
+ public Integer getEncodedValue(Value value) {
+ return values.getInt(value);
+ }
+
+ @Override
+ public int getBlockIndex(BasicBlock block) {
+ assert blocks.containsKey(block);
+ return blocks.getInt(block);
+ }
+
+ @Override
+ public LirStrategyInfo<Integer> getStrategyInfo() {
+ return new LirStrategyInfo<Integer>() {
+ @Override
+ public LirSsaValueStrategy<Integer> getReferenceStrategy() {
+ return referenceStrategy;
+ }
+ };
+ }
+ }
+
+ private static class DecodingStrategy extends LirDecodingStrategy<Value, Integer> {
+
+ private final Value[] values;
+
+ DecodingStrategy(LirCode<Integer> code) {
+ values = new Value[code.getArgumentCount() + code.getInstructionCount()];
+ }
+
+ @Override
+ public Value getValue(Integer encodedValue, LirStrategyInfo<Integer> strategyInfo) {
+ int index = encodedValue;
+ Value value = values[index];
+ if (value == null) {
+ value = new Value(index, TypeElement.getBottom(), null);
+ values[index] = value;
+ }
+ return value;
+ }
+
+ @Override
+ public Value getValueDefinitionForInstructionIndex(
+ int index, TypeElement type, Function<Integer, DebugLocalInfo> getLocalInfo) {
+ DebugLocalInfo localInfo = getLocalInfo.apply(index);
+ Value value = values[index];
+ if (value == null) {
+ value = new Value(index, type, localInfo);
+ values[index] = value;
+ } else {
+ value.setType(type);
+ if (localInfo != null) {
+ if (!value.hasLocalInfo()) {
+ value.setLocalInfo(localInfo);
+ }
+ assert localInfo == value.getLocalInfo();
+ }
+ }
+ return value;
+ }
+
+ @Override
+ public Phi getPhiDefinitionForInstructionIndex(
+ int valueIndex,
+ IntFunction<BasicBlock> getBlock,
+ TypeElement type,
+ Function<Integer, DebugLocalInfo> getLocalInfo,
+ LirStrategyInfo<Integer> strategyInfo) {
+ BasicBlock block = getBlock.apply(valueIndex);
+ DebugLocalInfo localInfo = getLocalInfo.apply(valueIndex);
+ Phi phi = new Phi(valueIndex, block, type, localInfo, RegisterReadType.NORMAL);
+ Value value = values[valueIndex];
+ if (value != null) {
+ // A fake ssa value has already been created, replace the users by the actual phi.
+ // TODO(b/225838009): We could consider encoding the value type as a bit in the value index
+ // and avoid the overhead of replacing users at phi-definition time.
+ assert !value.isPhi();
+ value.replaceUsers(phi);
+ }
+ values[valueIndex] = phi;
+ return phi;
+ }
+ }
+}
diff --git a/src/test/java/com/android/tools/r8/lightir/LirBasicCallbackTest.java b/src/test/java/com/android/tools/r8/lightir/LirBasicCallbackTest.java
index 062470c..abd980d 100644
--- a/src/test/java/com/android/tools/r8/lightir/LirBasicCallbackTest.java
+++ b/src/test/java/com/android/tools/r8/lightir/LirBasicCallbackTest.java
@@ -37,6 +37,11 @@
private static class ThrowingStrategy extends LirEncodingStrategy<Value, Integer> {
@Override
+ public boolean isPhiInlineInstruction() {
+ return false;
+ }
+
+ @Override
public void defineBlock(BasicBlock block, int index) {
throw new Unreachable();
}
@@ -62,7 +67,7 @@
}
@Override
- public LirSsaValueStrategy<Integer> getSsaValueStrategy() {
+ public LirStrategyInfo<Integer> getStrategyInfo() {
return null;
}
}
