| // 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.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; |
| import com.android.tools.r8.graph.DexType; |
| import com.android.tools.r8.graph.ProgramMethod; |
| import com.android.tools.r8.ir.analysis.type.TypeElement; |
| import com.android.tools.r8.ir.code.Argument; |
| import com.android.tools.r8.ir.code.ArrayLength; |
| import com.android.tools.r8.ir.code.BasicBlock; |
| import com.android.tools.r8.ir.code.CatchHandlers; |
| import com.android.tools.r8.ir.code.ConstNumber; |
| import com.android.tools.r8.ir.code.ConstString; |
| import com.android.tools.r8.ir.code.DebugLocalWrite; |
| import com.android.tools.r8.ir.code.DebugPosition; |
| import com.android.tools.r8.ir.code.Div; |
| import com.android.tools.r8.ir.code.Goto; |
| import com.android.tools.r8.ir.code.IRCode; |
| import com.android.tools.r8.ir.code.If; |
| import com.android.tools.r8.ir.code.If.Type; |
| import com.android.tools.r8.ir.code.Instruction; |
| import com.android.tools.r8.ir.code.InvokeDirect; |
| import com.android.tools.r8.ir.code.InvokeVirtual; |
| import com.android.tools.r8.ir.code.MoveException; |
| import com.android.tools.r8.ir.code.NumberGenerator; |
| import com.android.tools.r8.ir.code.NumericType; |
| import com.android.tools.r8.ir.code.Phi; |
| import com.android.tools.r8.ir.code.Phi.RegisterReadType; |
| import com.android.tools.r8.ir.code.Position; |
| import com.android.tools.r8.ir.code.Position.SyntheticPosition; |
| import com.android.tools.r8.ir.code.Return; |
| import com.android.tools.r8.ir.code.StaticGet; |
| import com.android.tools.r8.ir.code.Value; |
| import com.android.tools.r8.ir.conversion.MethodConversionOptions.MutableMethodConversionOptions; |
| import com.android.tools.r8.lightir.LIRCode.PositionEntry; |
| import com.android.tools.r8.utils.ListUtils; |
| import it.unimi.dsi.fastutil.ints.Int2ReferenceMap; |
| import it.unimi.dsi.fastutil.ints.Int2ReferenceOpenHashMap; |
| import it.unimi.dsi.fastutil.ints.IntArrayList; |
| import it.unimi.dsi.fastutil.ints.IntList; |
| import java.util.ArrayList; |
| import java.util.LinkedList; |
| import java.util.List; |
| |
| public class LIR2IRConverter { |
| |
| private LIR2IRConverter() {} |
| |
| public static IRCode translate(ProgramMethod method, LIRCode lirCode, AppView<?> appView) { |
| Parser parser = new Parser(lirCode, method.getReference(), appView); |
| parser.parseArguments(method); |
| lirCode.forEach(view -> view.accept(parser)); |
| return parser.getIRCode(method); |
| } |
| |
| /** |
| * When building IR the structured LIR parser is used to obtain the decoded operand indexes. The |
| * below parser subclass handles translation of indexes to SSA values. |
| */ |
| private static class Parser extends LIRParsedInstructionCallback { |
| |
| private static final int ENTRY_BLOCK_INDEX = -1; |
| |
| private final AppView<?> appView; |
| private final LIRCode code; |
| private final NumberGenerator valueNumberGenerator = new NumberGenerator(); |
| private final NumberGenerator basicBlockNumberGenerator = new NumberGenerator(); |
| |
| private final Value[] values; |
| private final Int2ReferenceMap<BasicBlock> blocks = new Int2ReferenceOpenHashMap<>(); |
| |
| private BasicBlock currentBlock = null; |
| private int nextInstructionIndex = 0; |
| |
| private Position currentPosition; |
| private PositionEntry nextPositionEntry = null; |
| private int nextIndexInPositionsTable = 0; |
| |
| public Parser(LIRCode code, DexMethod method, AppView<?> appView) { |
| super(code); |
| assert code.getPositionTable().length > 0; |
| assert code.getPositionTable()[0].fromInstructionIndex == 0; |
| this.appView = appView; |
| this.code = code; |
| values = new Value[code.getArgumentCount() + code.getInstructionCount()]; |
| // Recreate the preamble position. This is active for arguments and code with no positions. |
| currentPosition = SyntheticPosition.builder().setLine(0).setMethod(method).build(); |
| } |
| |
| @Override |
| public int getCurrentValueIndex() { |
| return nextInstructionIndex + code.getArgumentCount(); |
| } |
| |
| private void closeCurrentBlock() { |
| currentBlock = null; |
| } |
| |
| private void ensureCurrentBlock() { |
| // Control instructions must close the block, thus the current block is null iff the |
| // instruction denotes a new block. |
| if (currentBlock == null) { |
| currentBlock = blocks.computeIfAbsent(nextInstructionIndex, k -> new BasicBlock()); |
| CatchHandlers<Integer> handlers = |
| code.getTryCatchTable().getHandlersForBlock(nextInstructionIndex); |
| if (handlers != null) { |
| List<BasicBlock> targets = ListUtils.map(handlers.getAllTargets(), this::getBasicBlock); |
| targets.forEach(currentBlock::link); |
| currentBlock.linkCatchSuccessors(handlers.getGuards(), targets); |
| } |
| } else { |
| assert !blocks.containsKey(nextInstructionIndex); |
| } |
| } |
| |
| private void ensureCurrentPosition() { |
| if (nextPositionEntry != null |
| && nextPositionEntry.fromInstructionIndex <= nextInstructionIndex) { |
| currentPosition = nextPositionEntry.position; |
| advanceNextPositionEntry(); |
| } |
| } |
| |
| private void advanceNextPositionEntry() { |
| nextPositionEntry = |
| nextIndexInPositionsTable < code.getPositionTable().length |
| ? code.getPositionTable()[nextIndexInPositionsTable++] |
| : null; |
| } |
| |
| public void parseArguments(ProgramMethod method) { |
| currentBlock = getBasicBlock(ENTRY_BLOCK_INDEX); |
| boolean hasReceiverArgument = !method.getDefinition().isStatic(); |
| assert code.getArgumentCount() |
| == method.getParameters().size() + (hasReceiverArgument ? 1 : 0); |
| if (hasReceiverArgument) { |
| addThisArgument(method.getHolderType()); |
| } |
| int index = hasReceiverArgument ? 1 : 0; |
| for (DexType parameter : method.getParameters()) { |
| addArgument(parameter, index++); |
| } |
| // Set up position state after adding arguments. |
| advanceNextPositionEntry(); |
| } |
| |
| public IRCode getIRCode(ProgramMethod method) { |
| LinkedList<BasicBlock> blockList = new LinkedList<>(); |
| IntList blockIndices = new IntArrayList(blocks.keySet()); |
| blockIndices.sort(Integer::compare); |
| for (int i = 0; i < blockIndices.size(); i++) { |
| BasicBlock block = blocks.get(blockIndices.getInt(i)); |
| block.setFilled(); |
| blockList.add(block); |
| } |
| for (int i = 0; i < peekNextInstructionIndex(); ++i) { |
| valueNumberGenerator.next(); |
| } |
| return new IRCode( |
| appView.options(), |
| method, |
| Position.syntheticNone(), |
| blockList, |
| valueNumberGenerator, |
| basicBlockNumberGenerator, |
| code.getMetadata(), |
| method.getOrigin(), |
| new MutableMethodConversionOptions(appView.options())); |
| } |
| |
| public BasicBlock getBasicBlock(int instructionIndex) { |
| return blocks.computeIfAbsent( |
| instructionIndex, |
| k -> { |
| BasicBlock block = new BasicBlock(); |
| block.setNumber(basicBlockNumberGenerator.next()); |
| return block; |
| }); |
| } |
| |
| public Value getValue(int index) { |
| Value value = values[index]; |
| if (value == null) { |
| value = new Value(index, TypeElement.getBottom(), null); |
| values[index] = value; |
| } |
| return value; |
| } |
| |
| public List<Value> getValues(IntList indices) { |
| List<Value> arguments = new ArrayList<>(indices.size()); |
| for (int i = 0; i < indices.size(); i++) { |
| arguments.add(getValue(indices.getInt(i))); |
| } |
| return arguments; |
| } |
| |
| public int toInstructionIndexInIR(int lirIndex) { |
| return lirIndex + code.getArgumentCount(); |
| } |
| |
| public int peekNextInstructionIndex() { |
| return nextInstructionIndex; |
| } |
| |
| public Value getOutValueForNextInstruction(TypeElement type) { |
| int valueIndex = toInstructionIndexInIR(peekNextInstructionIndex()); |
| DebugLocalInfo localInfo = code.getDebugLocalInfo(valueIndex); |
| Value value = values[valueIndex]; |
| if (value == null) { |
| value = new Value(valueIndex, type, localInfo); |
| values[valueIndex] = value; |
| } else { |
| value.setType(type); |
| if (localInfo != null) { |
| value.setLocalInfo(localInfo); |
| } |
| } |
| return value; |
| } |
| |
| 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. |
| Phi phi = new Phi(valueIndex, currentBlock, 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; |
| } |
| |
| private void advanceInstructionState() { |
| ensureCurrentBlock(); |
| ensureCurrentPosition(); |
| ++nextInstructionIndex; |
| } |
| |
| private void addInstruction(Instruction instruction) { |
| int index = toInstructionIndexInIR(peekNextInstructionIndex()); |
| advanceInstructionState(); |
| instruction.setPosition(currentPosition); |
| currentBlock.getInstructions().add(instruction); |
| instruction.setBlock(currentBlock); |
| int[] debugEndIndices = code.getDebugLocalEnds(index); |
| if (debugEndIndices != null) { |
| for (int debugEndIndex : debugEndIndices) { |
| Value debugValue = getValue(debugEndIndex); |
| debugValue.addDebugLocalEnd(instruction); |
| } |
| } |
| } |
| |
| private void addThisArgument(DexType type) { |
| Argument argument = addArgument(type, 0); |
| argument.outValue().markAsThis(); |
| } |
| |
| private Argument addArgument(DexType type, int index) { |
| // 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 = new Value(index, typeElement, localInfo); |
| assert values[index] == null; |
| values[index] = dest; |
| Argument argument = new Argument(dest, index, type.isBooleanType()); |
| assert currentBlock != null; |
| assert currentPosition.isSyntheticPosition(); |
| argument.setPosition(currentPosition); |
| currentBlock.getInstructions().add(argument); |
| argument.setBlock(currentBlock); |
| return argument; |
| } |
| |
| @Override |
| public void onConstNull() { |
| Value dest = getOutValueForNextInstruction(TypeElement.getNull()); |
| addInstruction(new ConstNumber(dest, 0)); |
| } |
| |
| @Override |
| public void onConstInt(int value) { |
| Value dest = getOutValueForNextInstruction(TypeElement.getInt()); |
| addInstruction(new ConstNumber(dest, value)); |
| } |
| |
| @Override |
| public void onDivInt(int leftValueIndex, int rightValueIndex) { |
| Value dest = getOutValueForNextInstruction(TypeElement.getInt()); |
| addInstruction( |
| new Div(NumericType.INT, dest, getValue(leftValueIndex), getValue(rightValueIndex))); |
| } |
| |
| @Override |
| public void onConstString(DexString string) { |
| Value dest = getOutValueForNextInstruction(TypeElement.stringClassType(appView)); |
| addInstruction(new ConstString(dest, string)); |
| } |
| |
| @Override |
| public void onIf(Type ifKind, int blockIndex, int valueIndex) { |
| BasicBlock targetBlock = getBasicBlock(blockIndex); |
| Value value = getValue(valueIndex); |
| addInstruction(new If(ifKind, value)); |
| currentBlock.link(targetBlock); |
| currentBlock.link(getBasicBlock(nextInstructionIndex)); |
| closeCurrentBlock(); |
| } |
| |
| @Override |
| public void onFallthrough() { |
| int nextBlockIndex = peekNextInstructionIndex() + 1; |
| onGoto(nextBlockIndex); |
| } |
| |
| @Override |
| public void onGoto(int blockIndex) { |
| BasicBlock targetBlock = getBasicBlock(blockIndex); |
| addInstruction(new Goto()); |
| currentBlock.link(targetBlock); |
| closeCurrentBlock(); |
| } |
| |
| @Override |
| public void onInvokeDirect(DexMethod target, IntList arguments) { |
| // TODO(b/225838009): Maintain is-interface bit. |
| Value dest = getInvokeInstructionOutputValue(target); |
| List<Value> ssaArgumentValues = getValues(arguments); |
| InvokeDirect instruction = new InvokeDirect(target, dest, ssaArgumentValues); |
| addInstruction(instruction); |
| } |
| |
| @Override |
| public void onInvokeVirtual(DexMethod target, IntList arguments) { |
| // TODO(b/225838009): Maintain is-interface bit. |
| Value dest = getInvokeInstructionOutputValue(target); |
| List<Value> ssaArgumentValues = getValues(arguments); |
| InvokeVirtual instruction = new InvokeVirtual(target, dest, ssaArgumentValues); |
| addInstruction(instruction); |
| } |
| |
| private Value getInvokeInstructionOutputValue(DexMethod target) { |
| return target.getReturnType().isVoidType() |
| ? null |
| : getOutValueForNextInstruction(target.getReturnType().toTypeElement(appView)); |
| } |
| |
| @Override |
| public void onStaticGet(DexField field) { |
| Value dest = getOutValueForNextInstruction(field.getTypeElement(appView)); |
| addInstruction(new StaticGet(dest, field)); |
| } |
| |
| @Override |
| public void onReturnVoid() { |
| addInstruction(new Return()); |
| closeCurrentBlock(); |
| } |
| |
| @Override |
| public void onArrayLength(int arrayValueIndex) { |
| Value dest = getOutValueForNextInstruction(TypeElement.getInt()); |
| Value arrayValue = getValue(arrayValueIndex); |
| addInstruction(new ArrayLength(dest, arrayValue)); |
| } |
| |
| @Override |
| public void onDebugPosition() { |
| addInstruction(new DebugPosition()); |
| } |
| |
| @Override |
| public void onPhi(DexType type, IntList operands) { |
| Phi phi = getPhiForNextInstructionAndAdvanceState(type.toTypeElement(appView)); |
| List<Value> values = new ArrayList<>(operands.size()); |
| for (int i = 0; i < operands.size(); i++) { |
| values.add(getValue(operands.getInt(i))); |
| } |
| phi.addOperands(values); |
| } |
| |
| @Override |
| public void onMoveException(DexType exceptionType) { |
| Value dest = getOutValueForNextInstruction(exceptionType.toTypeElement(appView)); |
| addInstruction(new MoveException(dest, exceptionType, appView.options())); |
| } |
| |
| @Override |
| public void onDebugLocalWrite(int srcIndex) { |
| Value src = getValue(srcIndex); |
| // The type is in the local table, so initialize it with bottom and reset with the local info. |
| Value dest = getOutValueForNextInstruction(TypeElement.getBottom()); |
| TypeElement type = dest.getLocalInfo().type.toTypeElement(appView); |
| dest.setType(type); |
| addInstruction(new DebugLocalWrite(dest, src)); |
| } |
| } |
| } |