| // 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.DexItemFactory; |
| import com.android.tools.r8.ir.code.BasicBlock; |
| import com.android.tools.r8.ir.code.BasicBlockIterator; |
| import com.android.tools.r8.ir.code.CatchHandlers; |
| import com.android.tools.r8.ir.code.IRCode; |
| import com.android.tools.r8.ir.code.Instruction; |
| import com.android.tools.r8.ir.code.InstructionIterator; |
| import com.android.tools.r8.ir.code.Phi; |
| import com.android.tools.r8.ir.code.Value; |
| import com.android.tools.r8.lightir.LIRBuilder.BlockIndexGetter; |
| import com.android.tools.r8.utils.ListUtils; |
| import it.unimi.dsi.fastutil.ints.IntArrayList; |
| import it.unimi.dsi.fastutil.ints.IntList; |
| import it.unimi.dsi.fastutil.objects.Reference2IntMap; |
| import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap; |
| import it.unimi.dsi.fastutil.objects.Reference2ReferenceMap; |
| import it.unimi.dsi.fastutil.objects.Reference2ReferenceOpenHashMap; |
| import java.util.ArrayList; |
| import java.util.Arrays; |
| import java.util.Comparator; |
| import java.util.List; |
| |
| public class IR2LIRConverter { |
| |
| private final DexItemFactory factory; |
| private final IRCode irCode; |
| private final Reference2IntMap<BasicBlock> blocks = new Reference2IntOpenHashMap<>(); |
| private final Reference2IntMap<Value> values = new Reference2IntOpenHashMap<>(); |
| private final LIRBuilder<Value, BasicBlock> builder; |
| |
| private IR2LIRConverter(DexItemFactory factory, IRCode irCode) { |
| this.factory = factory; |
| this.irCode = irCode; |
| this.builder = |
| new LIRBuilder<Value, BasicBlock>( |
| irCode.context().getReference(), values::getInt, blocks::getInt, factory) |
| .setMetadata(irCode.metadata()); |
| } |
| |
| public static LIRCode translate(IRCode irCode, DexItemFactory factory) { |
| return new IR2LIRConverter(factory, irCode).internalTranslate(); |
| } |
| |
| private void recordBlock(BasicBlock block, int blockIndex) { |
| blocks.put(block, blockIndex); |
| } |
| |
| private void recordValue(Value value, int valueIndex) { |
| values.put(value, valueIndex); |
| if (value.hasLocalInfo()) { |
| builder.setDebugValue(value.getLocalInfo(), valueIndex); |
| } |
| } |
| |
| private LIRCode internalTranslate() { |
| irCode.traceBlocks(); |
| computeBlockAndValueTables(); |
| computeInstructions(); |
| return builder.build(); |
| } |
| |
| private void computeInstructions() { |
| // The IR instruction index corresponds to the LIR value index which includes arguments and |
| // all instructions. |
| int currentValueIndex = 0; |
| 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(), blocks::getInt); |
| 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 (block.hasCatchHandlers()) { |
| CatchHandlers<BasicBlock> handlers = block.getCatchHandlers(); |
| builder.addTryCatchHanders( |
| blocks.getInt(block), |
| new CatchHandlers<>( |
| handlers.getGuards(), ListUtils.map(handlers.getAllTargets(), blocks::getInt))); |
| } |
| InstructionIterator it = block.iterator(); |
| while (it.hasNext()) { |
| assert builder.verifyCurrentValueIndex(currentValueIndex); |
| Instruction instruction = it.next(); |
| assert !instruction.hasOutValue() |
| || currentValueIndex == values.getInt(instruction.outValue()); |
| builder.setCurrentPosition(instruction.getPosition()); |
| if (!instruction.getDebugValues().isEmpty()) { |
| builder.setDebugLocalEnds(currentValueIndex, instruction.getDebugValues()); |
| } |
| |
| if (instruction.isGoto()) { |
| BasicBlock nextBlock = blockIt.peekNext(); |
| if (instruction.asGoto().getTarget() == nextBlock) { |
| builder.addFallthrough(); |
| currentValueIndex++; |
| continue; |
| } |
| } |
| instruction.buildLIR(builder); |
| currentValueIndex++; |
| } |
| assert builder.verifyCurrentValueIndex(currentValueIndex); |
| } |
| } |
| |
| private void computeBlockAndValueTables() { |
| int instructionIndex = 0; |
| int valueIndex = 0; |
| for (BasicBlock block : irCode.blocks) { |
| recordBlock(block, instructionIndex); |
| for (Phi phi : block.getPhis()) { |
| recordValue(phi, valueIndex); |
| valueIndex++; |
| instructionIndex++; |
| } |
| for (Instruction instruction : block.getInstructions()) { |
| if (instruction.hasOutValue()) { |
| recordValue(instruction.outValue(), valueIndex); |
| } |
| valueIndex++; |
| if (!instruction.isArgument()) { |
| instructionIndex++; |
| } |
| } |
| } |
| } |
| |
| private static void permuteOperands(List<Value> operands, int[] permutation, Value[] output) { |
| for (int i = 0; i < operands.size(); i++) { |
| Value operand = operands.get(i); |
| output[permutation[i]] = operand; |
| } |
| } |
| |
| private static int[] computePermutation( |
| List<BasicBlock> originalPredecessors, BlockIndexGetter<BasicBlock> blockIndexGetter) { |
| int predecessorCount = originalPredecessors.size(); |
| // The final predecessor list is sorted by block order. |
| List<BasicBlock> sortedPredecessors = new ArrayList<>(originalPredecessors); |
| sortedPredecessors.sort(Comparator.comparingInt(blockIndexGetter::getBlockIndex)); |
| // Since predecessors are not unique, build a map from each unique block to its set of indices. |
| Reference2ReferenceMap<BasicBlock, IntList> mapping = |
| new Reference2ReferenceOpenHashMap<>(predecessorCount); |
| for (int originalIndex = 0; originalIndex < predecessorCount; originalIndex++) { |
| BasicBlock predecessor = originalPredecessors.get(originalIndex); |
| mapping.computeIfAbsent(predecessor, k -> new IntArrayList(1)).add(originalIndex); |
| } |
| // Assign an original index to each sorted index. |
| int[] permutation = new int[predecessorCount]; |
| for (int sortedIndex = 0; sortedIndex < predecessorCount; ) { |
| BasicBlock predecessor = sortedPredecessors.get(sortedIndex); |
| IntList originalIndices = mapping.get(predecessor); |
| assert verifySameBlock(sortedPredecessors, sortedIndex, originalIndices.size()); |
| for (int originalIndex : originalIndices) { |
| permutation[originalIndex] = sortedIndex++; |
| } |
| } |
| return permutation; |
| } |
| |
| private static boolean verifySameBlock(List<BasicBlock> predecessors, int startIndex, int size) { |
| if (size == 1) { |
| return true; |
| } |
| BasicBlock block = predecessors.get(startIndex); |
| for (int i = startIndex + 1; i < startIndex + size; i++) { |
| BasicBlock other = predecessors.get(i); |
| assert block == other; |
| } |
| return true; |
| } |
| } |