| // Copyright (c) 2016, 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.ir.conversion; |
| |
| import com.android.tools.r8.code.FillArrayData; |
| import com.android.tools.r8.code.FillArrayDataPayload; |
| import com.android.tools.r8.code.Format31t; |
| import com.android.tools.r8.code.Goto; |
| import com.android.tools.r8.code.Goto16; |
| import com.android.tools.r8.code.Goto32; |
| import com.android.tools.r8.code.IfEq; |
| import com.android.tools.r8.code.IfEqz; |
| import com.android.tools.r8.code.IfGe; |
| import com.android.tools.r8.code.IfGez; |
| import com.android.tools.r8.code.IfGt; |
| import com.android.tools.r8.code.IfGtz; |
| import com.android.tools.r8.code.IfLe; |
| import com.android.tools.r8.code.IfLez; |
| import com.android.tools.r8.code.IfLt; |
| import com.android.tools.r8.code.IfLtz; |
| import com.android.tools.r8.code.IfNe; |
| import com.android.tools.r8.code.IfNez; |
| import com.android.tools.r8.code.Instruction; |
| import com.android.tools.r8.code.Move16; |
| import com.android.tools.r8.code.MoveFrom16; |
| import com.android.tools.r8.code.MoveObject; |
| import com.android.tools.r8.code.MoveObject16; |
| import com.android.tools.r8.code.MoveObjectFrom16; |
| import com.android.tools.r8.code.MoveWide; |
| import com.android.tools.r8.code.MoveWide16; |
| import com.android.tools.r8.code.MoveWideFrom16; |
| import com.android.tools.r8.code.Nop; |
| import com.android.tools.r8.dex.Constants; |
| import com.android.tools.r8.errors.Unreachable; |
| import com.android.tools.r8.graph.DebugLocalInfo; |
| import com.android.tools.r8.graph.DexCode; |
| import com.android.tools.r8.graph.DexCode.Try; |
| import com.android.tools.r8.graph.DexCode.TryHandler; |
| import com.android.tools.r8.graph.DexCode.TryHandler.TypeAddrPair; |
| import com.android.tools.r8.graph.DexDebugEventBuilder; |
| import com.android.tools.r8.graph.DexItemFactory; |
| import com.android.tools.r8.graph.DexString; |
| import com.android.tools.r8.graph.DexType; |
| import com.android.tools.r8.ir.code.Argument; |
| import com.android.tools.r8.ir.code.BasicBlock; |
| import com.android.tools.r8.ir.code.CatchHandlers; |
| import com.android.tools.r8.ir.code.DebugPosition; |
| import com.android.tools.r8.ir.code.IRCode; |
| import com.android.tools.r8.ir.code.If; |
| import com.android.tools.r8.ir.code.InstructionIterator; |
| import com.android.tools.r8.ir.code.InstructionListIterator; |
| import com.android.tools.r8.ir.code.Move; |
| import com.android.tools.r8.ir.code.NewArrayFilledData; |
| import com.android.tools.r8.ir.code.Position; |
| import com.android.tools.r8.ir.code.Return; |
| import com.android.tools.r8.ir.code.Switch; |
| import com.android.tools.r8.ir.code.Value; |
| import com.android.tools.r8.ir.regalloc.LinearScanRegisterAllocator; |
| import com.android.tools.r8.ir.regalloc.RegisterAllocator; |
| import com.android.tools.r8.utils.InternalOptions; |
| import com.google.common.collect.BiMap; |
| import com.google.common.collect.HashBiMap; |
| import com.google.common.collect.Lists; |
| import com.google.common.collect.Sets; |
| import it.unimi.dsi.fastutil.ints.Int2ReferenceMap; |
| import it.unimi.dsi.fastutil.ints.Int2ReferenceMaps; |
| import it.unimi.dsi.fastutil.ints.Int2ReferenceOpenHashMap; |
| import java.util.ArrayList; |
| import java.util.List; |
| import java.util.ListIterator; |
| import java.util.Map; |
| import java.util.Set; |
| |
| /** |
| * Builder object for constructing dex bytecode from the high-level IR. |
| */ |
| public class DexBuilder { |
| |
| // The IR representation of the code to build. |
| private final IRCode ir; |
| |
| // The register allocator providing register assignments for the code to build. |
| private final RegisterAllocator registerAllocator; |
| |
| private final InternalOptions options; |
| |
| // List of information about switch payloads that have to be created at the end of the |
| // dex code. |
| private final List<SwitchPayloadInfo> switchPayloadInfos = new ArrayList<>(); |
| |
| // List of generated FillArrayData dex instructions. |
| private final List<FillArrayDataInfo> fillArrayDataInfos = new ArrayList<>(); |
| |
| // Set of if instructions that have offsets that are so large that they cannot be encoded in |
| // the if instruction format. |
| private Set<BasicBlock> ifsNeedingRewrite = Sets.newIdentityHashSet(); |
| |
| // Running bounds on offsets. |
| private int maxOffset = 0; |
| private int minOffset = 0; |
| |
| // Mapping from IR instructions to info for computing the dex translation. Use the |
| // getInfo/setInfo methods to access the mapping. |
| private Info[] instructionToInfo; |
| |
| // The number of ingoing and outgoing argument registers for the code. |
| private int inRegisterCount = 0; |
| private int outRegisterCount = 0; |
| |
| // The string reference in the code with the highest index. |
| private DexString highestSortingReferencedString = null; |
| |
| BasicBlock nextBlock; |
| |
| public DexBuilder( |
| IRCode ir, |
| RegisterAllocator registerAllocator, |
| InternalOptions options) { |
| assert ir != null; |
| assert registerAllocator != null; |
| this.ir = ir; |
| this.registerAllocator = registerAllocator; |
| this.options = options; |
| } |
| |
| private void reset() { |
| switchPayloadInfos.clear(); |
| fillArrayDataInfos.clear(); |
| ifsNeedingRewrite.clear(); |
| maxOffset = 0; |
| minOffset = 0; |
| instructionToInfo = new Info[instructionNumberToIndex(ir.numberRemainingInstructions())]; |
| inRegisterCount = 0; |
| outRegisterCount = 0; |
| highestSortingReferencedString = null; |
| nextBlock = null; |
| } |
| |
| /** |
| * Build the dex instructions added to this builder. |
| * |
| * This is a two pass construction that will first compute concrete offsets and then construct |
| * the concrete instructions. |
| */ |
| public DexCode build(int numberOfArguments) { |
| int numberOfInstructions; |
| int offset; |
| |
| do { |
| // Rewrite ifs that are know from the previous iteration to have offsets that are too |
| // large for the if encoding. |
| rewriteIfs(); |
| |
| // Reset the state of the builder to start from scratch. |
| reset(); |
| |
| // Remove redundant debug position instructions. They would otherwise materialize as |
| // unnecessary nops. |
| removeRedundantDebugPositions(); |
| |
| // Populate the builder info objects. |
| numberOfInstructions = 0; |
| |
| ListIterator<BasicBlock> iterator = ir.listIterator(); |
| assert iterator.hasNext(); |
| BasicBlock block = iterator.next(); |
| do { |
| nextBlock = iterator.hasNext() ? iterator.next() : null; |
| block.buildDex(this); |
| block = nextBlock; |
| } while (block != null); |
| |
| // Compute offsets. |
| offset = 0; |
| InstructionIterator it = ir.instructionIterator(); |
| while (it.hasNext()) { |
| Info info = getInfo(it.next()); |
| info.setOffset(offset); |
| offset += info.computeSize(this); |
| ++numberOfInstructions; |
| } |
| } while (!ifsNeedingRewrite.isEmpty()); |
| |
| // Build instructions. |
| DexDebugEventBuilder debugEventBuilder = new DexDebugEventBuilder(ir, options); |
| List<Instruction> dexInstructions = new ArrayList<>(numberOfInstructions); |
| int instructionOffset = 0; |
| InstructionIterator instructionIterator = ir.instructionIterator(); |
| while (instructionIterator.hasNext()) { |
| com.android.tools.r8.ir.code.Instruction ir = instructionIterator.next(); |
| Info info = getInfo(ir); |
| int previousInstructionCount = dexInstructions.size(); |
| info.addInstructions(this, dexInstructions); |
| int instructionStartOffset = instructionOffset; |
| if (previousInstructionCount < dexInstructions.size()) { |
| while (previousInstructionCount < dexInstructions.size()) { |
| Instruction instruction = dexInstructions.get(previousInstructionCount++); |
| instruction.setOffset(instructionOffset); |
| instructionOffset += instruction.getSize(); |
| } |
| } |
| debugEventBuilder.add(instructionStartOffset, instructionOffset, ir); |
| } |
| |
| ir.method.debugPositionRangeList = debugEventBuilder.buildPositionRanges(); |
| |
| // Compute switch payloads. |
| for (SwitchPayloadInfo switchPayloadInfo : switchPayloadInfos) { |
| // Align payloads at even addresses. |
| if (offset % 2 != 0) { |
| Nop nop = new Nop(); |
| nop.setOffset(offset++); |
| dexInstructions.add(nop); |
| } |
| // Create payload and add it to the instruction stream. |
| Nop payload = createSwitchPayload(switchPayloadInfo, offset); |
| payload.setOffset(offset); |
| offset += payload.getSize(); |
| dexInstructions.add(payload); |
| } |
| |
| // Compute fill array data payloads. |
| for (FillArrayDataInfo info : fillArrayDataInfos) { |
| // Align payloads at even addresses. |
| if (offset % 2 != 0) { |
| Nop nop = new Nop(); |
| nop.setOffset(offset++); |
| dexInstructions.add(nop); |
| } |
| // Create payload and add it to the instruction stream. |
| FillArrayDataPayload payload = info.ir.createPayload(); |
| payload.setOffset(offset); |
| info.dex.setPayloadOffset(offset - info.dex.getOffset()); |
| offset += payload.getSize(); |
| dexInstructions.add(payload); |
| } |
| |
| // Construct try-catch info. |
| TryInfo tryInfo = computeTryInfo(); |
| |
| // Return the dex code. |
| DexCode code = new DexCode( |
| registerAllocator.registersUsed(), |
| inRegisterCount, |
| outRegisterCount, |
| dexInstructions.toArray(new Instruction[dexInstructions.size()]), tryInfo.tries, |
| tryInfo.handlers, |
| debugEventBuilder.build(), |
| highestSortingReferencedString); |
| |
| return code; |
| } |
| |
| private static boolean verifyNopHasNoPosition( |
| com.android.tools.r8.ir.code.Instruction instruction, ListIterator<BasicBlock> blocks) { |
| BasicBlock nextBlock = null; |
| if (blocks.hasNext()) { |
| nextBlock = blocks.next(); |
| blocks.previous(); |
| } |
| return verifyNopHasNoPosition(instruction, nextBlock); |
| } |
| |
| private static boolean verifyNopHasNoPosition( |
| com.android.tools.r8.ir.code.Instruction instruction, BasicBlock nextBlock) { |
| if (isNopInstruction(instruction, nextBlock)) { |
| assert instruction.getPosition().isNone(); |
| } |
| return true; |
| } |
| |
| // Eliminates unneeded debug positions. |
| // |
| // After this pass all instructions that don't materialize to an actual DEX instruction will have |
| // Position.none(). If any other instruction has a non-none position then all other instructions |
| // that do materialize to a DEX instruction (eg, non-fallthrough gotos) will have a non-none |
| // position. |
| // |
| // Remaining debug positions indicate two successive lines without intermediate instructions. |
| // For these we must emit a nop instruction to ensure they don't share the same pc. |
| private void removeRedundantDebugPositions() { |
| if (!ir.hasDebugPositions) { |
| return; |
| } |
| Int2ReferenceMap[] localsMap = new Int2ReferenceMap[instructionToInfo.length]; |
| // Scan forwards removing debug positions equal to the previous instruction position. |
| { |
| Int2ReferenceMap<DebugLocalInfo> locals = Int2ReferenceMaps.emptyMap(); |
| Position previous = Position.none(); |
| ListIterator<BasicBlock> blockIterator = ir.listIterator(); |
| BasicBlock previousBlock = null; |
| while (blockIterator.hasNext()) { |
| BasicBlock block = blockIterator.next(); |
| if (previousBlock != null |
| && previousBlock.exit().isGoto() |
| && !isNopInstruction(previousBlock.exit(), block)) { |
| assert previousBlock.exit().getPosition().isNone() |
| || previousBlock.exit().getPosition().equals(previous); |
| previousBlock.exit().forceSetPosition(previous); |
| } |
| InstructionListIterator instructionIterator = block.listIterator(); |
| if (block.getLocalsAtEntry() != null && !locals.equals(block.getLocalsAtEntry())) { |
| locals = new Int2ReferenceOpenHashMap<>(block.getLocalsAtEntry()); |
| } |
| while (instructionIterator.hasNext()) { |
| com.android.tools.r8.ir.code.Instruction instruction = instructionIterator.next(); |
| if (instruction.isDebugPosition() && previous.equals(instruction.getPosition())) { |
| instructionIterator.remove(); |
| } else if (instruction.isConstNumber() && !instruction.outValue().needsRegister()) { |
| instruction.forceSetPosition(Position.none()); |
| } else if (instruction.getPosition().isSome()) { |
| assert verifyNopHasNoPosition(instruction, blockIterator); |
| previous = instruction.getPosition(); |
| } |
| if (instruction.isDebugLocalsChange()) { |
| locals = new Int2ReferenceOpenHashMap<>(locals); |
| instruction.asDebugLocalsChange().apply(locals); |
| } |
| localsMap[instructionNumberToIndex(instruction.getNumber())] = locals; |
| } |
| previousBlock = block; |
| } |
| if (previousBlock != null && previousBlock.exit().isGoto()) { |
| // If the last block ends in a goto it cannot be a fallthrough/nop. |
| assert previousBlock.exit().getPosition().isNone(); |
| previousBlock.exit().forceSetPosition(previous); |
| } |
| } |
| // Scan backwards removing debug positions equal to the following instruction position. |
| { |
| ListIterator<BasicBlock> blocks = ir.blocks.listIterator(ir.blocks.size()); |
| BasicBlock block = null; |
| BasicBlock nextBlock; |
| com.android.tools.r8.ir.code.Instruction next = null; |
| Int2ReferenceMap nextLocals = null; |
| while (blocks.hasPrevious()) { |
| nextBlock = block; |
| block = blocks.previous(); |
| InstructionListIterator instructions = block.listIterator(block.getInstructions().size()); |
| while (instructions.hasPrevious()) { |
| com.android.tools.r8.ir.code.Instruction instruction = instructions.previous(); |
| int index = instructionNumberToIndex(instruction.getNumber()); |
| if (instruction.isDebugPosition() && localsMap[index].equals(nextLocals)) { |
| Position nextPosition = next.getPosition(); |
| Position thisPosition = instruction.getPosition(); |
| if (nextPosition.isNone()) { |
| next.forceSetPosition(thisPosition); |
| instructions.remove(); |
| } else if (nextPosition.equals(thisPosition)) { |
| instructions.remove(); |
| } else { |
| next = instruction; |
| } |
| } else { |
| assert verifyNopHasNoPosition(instruction, nextBlock); |
| if (!isNopInstruction(instruction, nextBlock)) { |
| next = instruction; |
| nextLocals = localsMap[index]; |
| assert nextLocals != null; |
| } |
| } |
| } |
| } |
| } |
| } |
| |
| // Rewrite ifs with offsets that are too large for the if encoding. The rewriting transforms: |
| // |
| // |
| // BB0: if condition goto BB_FAR_AWAY |
| // BB1: ... |
| // |
| // to: |
| // |
| // BB0: if !condition goto BB1 |
| // BB2: goto BB_FAR_AWAY |
| // BB1: ... |
| private void rewriteIfs() { |
| if (ifsNeedingRewrite.isEmpty()) { |
| return; |
| } |
| ListIterator<BasicBlock> it = ir.blocks.listIterator(); |
| while (it.hasNext()) { |
| BasicBlock block = it.next(); |
| if (ifsNeedingRewrite.contains(block)) { |
| If theIf = block.exit().asIf(); |
| BasicBlock trueTarget = theIf.getTrueTarget(); |
| BasicBlock newBlock = BasicBlock.createGotoBlock(trueTarget, ir.blocks.size()); |
| theIf.setTrueTarget(newBlock); |
| theIf.invert(); |
| it.add(newBlock); |
| } |
| } |
| } |
| |
| private void needsIfRewriting(BasicBlock block) { |
| ifsNeedingRewrite.add(block); |
| } |
| |
| public void registerStringReference(DexString string) { |
| if (highestSortingReferencedString == null |
| || string.slowCompareTo(highestSortingReferencedString) > 0) { |
| highestSortingReferencedString = string; |
| } |
| } |
| |
| public void requestOutgoingRegisters(int requiredRegisterCount) { |
| if (requiredRegisterCount > outRegisterCount) { |
| outRegisterCount = requiredRegisterCount; |
| } |
| } |
| |
| public int allocatedRegister(Value value, int instructionNumber) { |
| return registerAllocator.getRegisterForValue(value, instructionNumber); |
| } |
| |
| // Get the argument register for a value if it is an argument, otherwise returns the |
| // allocated register at the instruction number. |
| public int argumentOrAllocateRegister(Value value, int instructionNumber) { |
| return registerAllocator.getArgumentOrAllocateRegisterForValue(value, instructionNumber); |
| } |
| |
| public boolean argumentValueUsesHighRegister(Value value, int instructionNumber) { |
| return registerAllocator.argumentValueUsesHighRegister(value, instructionNumber); |
| } |
| |
| public void addGoto(com.android.tools.r8.ir.code.Goto jump) { |
| if (jump.getTarget() != nextBlock) { |
| add(jump, new GotoInfo(jump)); |
| } else { |
| addNop(jump); |
| } |
| } |
| |
| public void addIf(If branch) { |
| assert nextBlock == branch.fallthroughBlock(); |
| add(branch, new IfInfo(branch)); |
| } |
| |
| public void addMove(Move move) { |
| add(move, new MoveInfo(move)); |
| } |
| |
| public void addNop(com.android.tools.r8.ir.code.Instruction instruction) { |
| assert instruction.getPosition().isNone(); |
| add(instruction, new FallThroughInfo(instruction)); |
| } |
| |
| private static boolean isNopInstruction( |
| com.android.tools.r8.ir.code.Instruction instruction, BasicBlock nextBlock) { |
| return instruction.isArgument() |
| || instruction.isDebugLocalsChange() |
| || (instruction.isConstNumber() && !instruction.outValue().needsRegister()) |
| || (instruction.isGoto() && instruction.asGoto().getTarget() == nextBlock); |
| } |
| |
| public void addDebugPosition(DebugPosition position) { |
| // Remaining debug positions always require we emit an actual nop instruction. |
| // See removeRedundantDebugPositions. |
| add(position, new FixedSizeInfo(position, new Nop())); |
| } |
| |
| public void add(com.android.tools.r8.ir.code.Instruction ir, Instruction dex) { |
| assert !ir.isGoto(); |
| add(ir, new FixedSizeInfo(ir, dex)); |
| } |
| |
| public void add(com.android.tools.r8.ir.code.Instruction ir, Instruction[] dex) { |
| assert !ir.isGoto(); |
| add(ir, new MultiFixedSizeInfo(ir, dex)); |
| } |
| |
| public void addSwitch(Switch s, Format31t dex) { |
| assert nextBlock == s.fallthroughBlock(); |
| switchPayloadInfos.add(new SwitchPayloadInfo(s, dex)); |
| add(s, dex); |
| } |
| |
| public void addFillArrayData(NewArrayFilledData nafd, FillArrayData dex) { |
| fillArrayDataInfos.add(new FillArrayDataInfo(nafd, dex)); |
| add(nafd, dex); |
| } |
| |
| public void addArgument(Argument argument) { |
| inRegisterCount += argument.outValue().requiredRegisters(); |
| add(argument, new FallThroughInfo(argument)); |
| } |
| |
| public void addReturn(Return ret, Instruction dex) { |
| if (nextBlock != null |
| && ret.identicalAfterRegisterAllocation(nextBlock.entry(), registerAllocator)) { |
| ret.forceSetPosition(Position.none()); |
| addNop(ret); |
| } else { |
| add(ret, dex); |
| } |
| } |
| |
| private void add(com.android.tools.r8.ir.code.Instruction ir, Info info) { |
| assert ir != null; |
| assert info != null; |
| assert getInfo(ir) == null; |
| info.setMinOffset(minOffset); |
| info.setMaxOffset(maxOffset); |
| minOffset += info.minSize(); |
| maxOffset += info.maxSize(); |
| setInfo(ir, info); |
| } |
| |
| private static int instructionNumberToIndex(int instructionNumber) { |
| return instructionNumber / LinearScanRegisterAllocator.INSTRUCTION_NUMBER_DELTA; |
| } |
| |
| // Helper used by the info objects. |
| private Info getInfo(com.android.tools.r8.ir.code.Instruction instruction) { |
| return instructionToInfo[instructionNumberToIndex(instruction.getNumber())]; |
| } |
| |
| private void setInfo(com.android.tools.r8.ir.code.Instruction instruction, Info info) { |
| instructionToInfo[instructionNumberToIndex(instruction.getNumber())] = info; |
| } |
| |
| private Info getTargetInfo(BasicBlock block) { |
| InstructionIterator iterator = block.iterator(); |
| com.android.tools.r8.ir.code.Instruction instruction = null; |
| while (iterator.hasNext()) { |
| instruction = iterator.next(); |
| Info info = getInfo(instruction); |
| if (!(info instanceof FallThroughInfo)) { |
| return info; |
| } |
| } |
| assert instruction != null; |
| if (instruction.isReturn()) { |
| assert getInfo(instruction) instanceof FallThroughInfo; |
| return getTargetInfo(computeNextBlock(block)); |
| } |
| assert instruction.isGoto(); |
| return getTargetInfo(instruction.asGoto().getTarget()); |
| } |
| |
| private BasicBlock computeNextBlock(BasicBlock block) { |
| ListIterator<BasicBlock> it = ir.listIterator(); |
| BasicBlock current = it.next(); |
| while (current != block) { |
| current = it.next(); |
| } |
| return it.next(); |
| } |
| |
| // Helper for computing switch payloads. |
| private Nop createSwitchPayload(SwitchPayloadInfo info, int offset) { |
| Switch ir = info.ir; |
| // Patch the payload offset in the generated switch instruction now |
| // that the location is known. |
| info.dex.setPayloadOffset(offset - getInfo(ir).getOffset()); |
| // Compute target offset for each of the keys based on the offset of the |
| // first instruction in the block that the switch goes to for that key. |
| int[] targetBlockIndices = ir.targetBlockIndices(); |
| int[] targets = new int[targetBlockIndices.length]; |
| for (int i = 0; i < targetBlockIndices.length; i++) { |
| BasicBlock targetBlock = ir.targetBlock(i); |
| com.android.tools.r8.ir.code.Instruction targetInstruction = targetBlock.entry(); |
| targets[i] = getInfo(targetInstruction).getOffset() - getInfo(ir).getOffset(); |
| } |
| BasicBlock fallthroughBlock = ir.fallthroughBlock(); |
| com.android.tools.r8.ir.code.Instruction fallthroughTargetInstruction = |
| fallthroughBlock.entry(); |
| int fallthroughTarget = |
| getInfo(fallthroughTargetInstruction).getOffset() - getInfo(ir).getOffset(); |
| |
| return ir.buildPayload(targets, fallthroughTarget); |
| } |
| |
| // Helpers for computing the try items and handlers. |
| |
| private TryInfo computeTryInfo() { |
| // Canonical map of handlers. |
| BiMap<CatchHandlers<BasicBlock>, Integer> canonicalHandlers = HashBiMap.create(); |
| // Compute the list of try items and their handlers. |
| List<TryItem> tryItems = computeTryItems(canonicalHandlers); |
| // Compute handler sets before dex items which depend on the handler index. |
| Try[] tries = getDexTryItems(tryItems, canonicalHandlers); |
| TryHandler[] handlers = getDexTryHandlers(canonicalHandlers.inverse()); |
| return new TryInfo(tries, handlers); |
| } |
| |
| private List<TryItem> computeTryItems( |
| BiMap<CatchHandlers<BasicBlock>, Integer> handlerToIndex) { |
| BiMap<Integer, CatchHandlers<BasicBlock>> indexToHandler = handlerToIndex.inverse(); |
| List<TryItem> tryItems = new ArrayList<>(); |
| List<BasicBlock> blocksWithHandlers = new ArrayList<>(); |
| TryItem currentTryItem = null; |
| // Create try items with maximal ranges to get as much coalescing as possible. After coalescing |
| // the try ranges are trimmed. |
| for (BasicBlock block : ir.blocks) { |
| CatchHandlers<BasicBlock> handlers = block.getCatchHandlers(); |
| // If this assert is hit, then the block contains no instruction that can throw. This is most |
| // likely due to dead-code elimination or other optimizations that might now work on a refined |
| // notion of what can throw. If so, the trivial blocks should either be removed or their catch |
| // handlers deleted to reflect the simpler graph prior to building the dex code. |
| assert handlers.isEmpty() || block.canThrow(); |
| if (!handlers.isEmpty()) { |
| if (handlerToIndex.containsKey(handlers)) { |
| handlers = indexToHandler.get(handlerToIndex.get(handlers)); |
| } else { |
| handlerToIndex.put(handlers, handlerToIndex.size()); |
| } |
| Info startInfo = getInfo(block.entry()); |
| Info endInfo = getInfo(block.exit()); |
| int start = startInfo.getOffset(); |
| int end = endInfo.getOffset() + endInfo.getSize(); |
| currentTryItem = new TryItem(handlers, start, end); |
| tryItems.add(currentTryItem); |
| blocksWithHandlers.add(block); |
| } else if (currentTryItem != null && !block.canThrow()) { |
| Info endInfo = getInfo(block.exit()); |
| // If the block only contains a goto there might not be an info for the exit instruction. |
| if (endInfo != null) { |
| currentTryItem.end = endInfo.getOffset() + endInfo.getSize(); |
| } |
| } else { |
| currentTryItem = null; |
| } |
| } |
| |
| // If there are no try items it is trivially coalesced. |
| if (tryItems.isEmpty()) { |
| return tryItems; |
| } |
| |
| // Coalesce try blocks. |
| tryItems.sort(TryItem::compareTo); |
| List<TryItem> coalescedTryItems = new ArrayList<>(tryItems.size()); |
| TryItem item = null; |
| for (int i = 0; i < tryItems.size(); ) { |
| if (item != null) { |
| item.end = trimEnd(blocksWithHandlers.get(i - 1)); |
| } |
| item = tryItems.get(i); |
| coalescedTryItems.add(item); |
| // Trim the range start for non-throwing instructions when starting a new range. |
| List<com.android.tools.r8.ir.code.Instruction> instructions = blocksWithHandlers.get(i).getInstructions(); |
| for (com.android.tools.r8.ir.code.Instruction insn : instructions) { |
| if (insn.instructionTypeCanThrow()) { |
| item.start = getInfo(insn).getOffset(); |
| break; |
| } |
| } |
| // Append all consecutive ranges that define the same handlers. |
| ++i; |
| while (i < tryItems.size()) { |
| TryItem next = tryItems.get(i); |
| if (item.end != next.start || !item.handlers.equals(next.handlers)) { |
| break; |
| } |
| item.end = next.end; |
| ++i; |
| } |
| } |
| // Trim the last try range. |
| int lastIndex = tryItems.size() - 1; |
| item.end = trimEnd(blocksWithHandlers.get(lastIndex)); |
| return coalescedTryItems; |
| } |
| |
| private int trimEnd(BasicBlock block) { |
| // Trim the range end for non-throwing instructions when end has been computed. |
| List<com.android.tools.r8.ir.code.Instruction> instructions = block.getInstructions(); |
| for (com.android.tools.r8.ir.code.Instruction insn : Lists.reverse(instructions)) { |
| if (insn.instructionTypeCanThrow()) { |
| Info info = getInfo(insn); |
| return info.getOffset() + info.getSize(); |
| } |
| } |
| throw new Unreachable("Expected to find a possibly throwing instruction"); |
| } |
| |
| private static Try[] getDexTryItems(List<TryItem> tryItems, |
| Map<CatchHandlers<BasicBlock>, Integer> catchHandlers) { |
| Try[] tries = new Try[tryItems.size()]; |
| for (int i = 0; i < tries.length; ++i) { |
| TryItem item = tryItems.get(i); |
| Try dexTry = new Try(item.start, item.end - item.start, -1); |
| dexTry.handlerIndex = catchHandlers.get(item.handlers); |
| tries[i] = dexTry; |
| } |
| return tries; |
| } |
| |
| private TryHandler[] getDexTryHandlers(Map<Integer, CatchHandlers<BasicBlock>> catchHandlers) { |
| TryHandler[] handlers = new TryHandler[catchHandlers.size()]; |
| for (int j = 0; j < catchHandlers.size(); j++) { |
| CatchHandlers<BasicBlock> handlerGroup = catchHandlers.get(j); |
| int catchAllOffset = TryHandler.NO_HANDLER; |
| List<TypeAddrPair> pairs = new ArrayList<>(); |
| for (int i = 0; i < handlerGroup.getGuards().size(); i++) { |
| DexType type = handlerGroup.getGuards().get(i); |
| BasicBlock target = handlerGroup.getAllTargets().get(i); |
| int targetOffset = getInfo(target.entry()).getOffset(); |
| if (type == DexItemFactory.catchAllType) { |
| assert i == handlerGroup.getGuards().size() - 1; |
| catchAllOffset = targetOffset; |
| } else { |
| pairs.add(new TypeAddrPair(type, targetOffset)); |
| } |
| } |
| TypeAddrPair[] pairsArray = pairs.toArray(new TypeAddrPair[pairs.size()]); |
| handlers[j] = new TryHandler(pairsArray, catchAllOffset); |
| } |
| return handlers; |
| } |
| |
| // Dex instruction wrapper with information to compute instruction sizes and offsets for jumps. |
| private static abstract class Info { |
| |
| private final com.android.tools.r8.ir.code.Instruction ir; |
| // Concrete final offset of the instruction. |
| private int offset = -1; |
| // Lower and upper bound of the final offset. |
| private int minOffset = -1; |
| private int maxOffset = -1; |
| |
| public Info(com.android.tools.r8.ir.code.Instruction ir) { |
| assert ir != null; |
| this.ir = ir; |
| } |
| |
| // Computes the final size of the instruction. |
| // All instruction offsets up-to and including this instruction will be defined at this point. |
| public abstract int computeSize(DexBuilder builder); |
| |
| // Materialize the actual construction. |
| // All instruction offsets are known at this point. |
| public abstract void addInstructions(DexBuilder builder, List<Instruction> instructions); |
| |
| // Lower bound on the size of the instruction. |
| public abstract int minSize(); |
| |
| // Upper bound on the size of the instruction. |
| public abstract int maxSize(); |
| |
| public abstract int getSize(); |
| |
| public int getOffset() { |
| assert offset >= 0 : this; |
| return offset; |
| } |
| |
| public void setOffset(int offset) { |
| assert offset >= 0; |
| this.offset = offset; |
| } |
| |
| public int getMinOffset() { |
| assert minOffset >= 0; |
| return minOffset; |
| } |
| |
| public void setMinOffset(int minOffset) { |
| assert minOffset >= 0; |
| this.minOffset = minOffset; |
| } |
| |
| public int getMaxOffset() { |
| assert maxOffset >= 0; |
| return maxOffset; |
| } |
| |
| public void setMaxOffset(int maxOffset) { |
| assert maxOffset >= 0; |
| this.maxOffset = maxOffset; |
| } |
| |
| public com.android.tools.r8.ir.code.Instruction getIR() { |
| return ir; |
| } |
| } |
| |
| private static class FixedSizeInfo extends Info { |
| |
| private Instruction instruction; |
| |
| public FixedSizeInfo(com.android.tools.r8.ir.code.Instruction ir, Instruction instruction) { |
| super(ir); |
| this.instruction = instruction; |
| } |
| |
| @Override |
| public int getSize() { |
| return instruction.getSize(); |
| } |
| |
| @Override |
| public int minSize() { |
| return instruction.getSize(); |
| } |
| |
| @Override |
| public int maxSize() { |
| return instruction.getSize(); |
| } |
| |
| @Override |
| public int computeSize(DexBuilder builder) { |
| instruction.setOffset(getOffset()); // for better printing of the dex code. |
| return instruction.getSize(); |
| } |
| |
| @Override |
| public void addInstructions(DexBuilder builder, List<Instruction> instructions) { |
| instructions.add(instruction); |
| } |
| } |
| |
| private static class MultiFixedSizeInfo extends Info { |
| |
| private Instruction[] instructions; |
| private final int size; |
| |
| public MultiFixedSizeInfo(com.android.tools.r8.ir.code.Instruction ir, Instruction[] instructions) { |
| super(ir); |
| this.instructions = instructions; |
| int size = 0; |
| for (Instruction instruction : instructions) { |
| size += instruction.getSize(); |
| } |
| this.size = size; |
| } |
| |
| @Override |
| public int computeSize(DexBuilder builder) { |
| return size; |
| } |
| |
| @Override |
| public void addInstructions(DexBuilder builder, List<Instruction> instructions) { |
| int offset = getOffset(); |
| for (Instruction instruction : this.instructions) { |
| instructions.add(instruction); |
| instruction.setOffset(offset); |
| offset += instruction.getSize(); |
| } |
| } |
| |
| @Override |
| public int minSize() { |
| return size; |
| } |
| |
| @Override |
| public int maxSize() { |
| return size; |
| } |
| |
| @Override |
| public int getSize() { |
| return size; |
| } |
| } |
| |
| private static class FallThroughInfo extends Info { |
| |
| public FallThroughInfo(com.android.tools.r8.ir.code.Instruction ir) { |
| super(ir); |
| } |
| |
| @Override |
| public int getSize() { |
| return 0; |
| } |
| |
| @Override |
| public int computeSize(DexBuilder builder) { |
| return 0; |
| } |
| |
| @Override |
| public void addInstructions(DexBuilder builder, List<Instruction> instructions) { |
| } |
| |
| @Override |
| public int minSize() { |
| return 0; |
| } |
| |
| @Override |
| public int maxSize() { |
| return 0; |
| } |
| } |
| |
| private static class GotoInfo extends Info { |
| |
| private int size = -1; |
| |
| public GotoInfo(com.android.tools.r8.ir.code.Goto jump) { |
| super(jump); |
| } |
| |
| private com.android.tools.r8.ir.code.Goto getJump() { |
| return (com.android.tools.r8.ir.code.Goto) getIR(); |
| } |
| |
| @Override |
| public int getSize() { |
| assert size > 0; |
| return size; |
| } |
| |
| @Override |
| public int minSize() { |
| assert new Goto(42).getSize() == 1; |
| return 1; |
| } |
| |
| @Override |
| public int maxSize() { |
| assert new Goto32(0).getSize() == 3; |
| return 3; |
| } |
| |
| @Override |
| public int computeSize(DexBuilder builder) { |
| assert size < 0; |
| com.android.tools.r8.ir.code.Goto jump = getJump(); |
| Info targetInfo = builder.getTargetInfo(jump.getTarget()); |
| // Trivial loop will be emitted as: nop & goto -1 |
| if (jump == targetInfo.getIR()) { |
| size = 2; |
| return size; |
| } |
| int maxOffset = getMaxOffset(); |
| int maxTargetOffset = targetInfo.getMaxOffset(); |
| int delta; |
| if (maxTargetOffset < maxOffset) { |
| // Backward branch: compute exact size (the target offset is set). |
| delta = getOffset() - targetInfo.getOffset(); |
| } else { |
| // Forward branch: over estimate the distance, but take into account the sizes |
| // of instructions generated so far. That way the over estimation is only for the |
| // instructions between this one and the target. |
| int maxOverEstimation = maxOffset - getOffset(); |
| delta = (maxTargetOffset - maxOverEstimation) - getOffset(); |
| } |
| if (delta <= Byte.MAX_VALUE) { |
| size = 1; |
| } else if (delta <= Short.MAX_VALUE) { |
| size = 2; |
| } else { |
| size = 3; |
| } |
| if (targetInfo.getIR().isReturn() && targetInfo.getIR().getPosition().isNone()) { |
| // Set the size to the min of the size of the return and the size of the goto. When |
| // adding instructions, we use the return if the computed size matches the size of the |
| // return. |
| assert !(targetInfo instanceof FallThroughInfo); |
| size = Math.min(targetInfo.getSize(), size); |
| } |
| assert size != 0; |
| return size; |
| } |
| |
| @Override |
| public void addInstructions(DexBuilder builder, List<Instruction> instructions) { |
| com.android.tools.r8.ir.code.Goto jump = getJump(); |
| int source = builder.getInfo(jump).getOffset(); |
| Info targetInfo = builder.getTargetInfo(jump.getTarget()); |
| int relativeOffset = targetInfo.getOffset() - source; |
| // Emit a return if the target is a return and the size of the return is the computed |
| // size of this instruction. |
| Return ret = targetInfo.getIR().asReturn(); |
| if (ret != null && size == targetInfo.getSize() && ret.getPosition().isNone()) { |
| Instruction dex = ret.createDexInstruction(builder); |
| dex.setOffset(getOffset()); // for better printing of the dex code. |
| instructions.add(dex); |
| } else if (size == relativeOffset) { |
| // We should never generate a goto targeting the next instruction. However, if we do |
| // we replace it with nops. This works around a dalvik bug where the dalvik tracing |
| // jit crashes on 'goto next instruction' on Android 4.1.1. |
| // TODO(b/34726595): We currently do hit this case and we should see if we can avoid that. |
| for (int i = 0; i < size; i++) { |
| Instruction dex = new Nop(); |
| assert dex.getSize() == 1; |
| dex.setOffset(getOffset() + i); // for better printing of the dex code. |
| instructions.add(dex); |
| } |
| } else { |
| Instruction dex; |
| switch (size) { |
| case 1: |
| assert relativeOffset != 0; |
| dex = new Goto(relativeOffset); |
| break; |
| case 2: |
| if (relativeOffset == 0) { |
| Nop nop = new Nop(); |
| instructions.add(nop); |
| dex = new Goto(-nop.getSize()); |
| } else { |
| dex = new Goto16(relativeOffset); |
| } |
| break; |
| case 3: |
| dex = new Goto32(relativeOffset); |
| break; |
| default: |
| throw new Unreachable("Unexpected size for goto instruction: " + size); |
| } |
| dex.setOffset(getOffset()); // for better printing of the dex code. |
| instructions.add(dex); |
| } |
| } |
| } |
| |
| public static class IfInfo extends Info { |
| |
| private int size = -1; |
| |
| public IfInfo(If branch) { |
| super(branch); |
| } |
| |
| private If getBranch() { |
| return (If) getIR(); |
| } |
| |
| private boolean branchesToSelf(DexBuilder builder) { |
| If branch = getBranch(); |
| Info trueTargetInfo = builder.getTargetInfo(branch.getTrueTarget()); |
| return branch == trueTargetInfo.getIR(); |
| } |
| |
| private boolean offsetOutOfRange(DexBuilder builder) { |
| Info targetInfo = builder.getTargetInfo(getBranch().getTrueTarget()); |
| int maxOffset = getMaxOffset(); |
| int maxTargetOffset = targetInfo.getMaxOffset(); |
| if (maxTargetOffset < maxOffset) { |
| return getOffset() - targetInfo.getOffset() < Short.MIN_VALUE; |
| } |
| // Forward branch: over estimate the distance, but take into account the sizes |
| // of instructions generated so far. That way the over estimation is only for the |
| // instructions between this one and the target. |
| int maxOverEstimation = maxOffset - getOffset(); |
| return (maxTargetOffset - maxOverEstimation) - getOffset() > Short.MAX_VALUE; |
| } |
| |
| @Override |
| public void addInstructions(DexBuilder builder, List<Instruction> instructions) { |
| If branch = getBranch(); |
| int source = builder.getInfo(branch).getOffset(); |
| int target = builder.getInfo(branch.getTrueTarget().entry()).getOffset(); |
| int relativeOffset = target - source; |
| int register1 = builder.allocatedRegister(branch.inValues().get(0), branch.getNumber()); |
| if (size == 3) { |
| assert branchesToSelf(builder); |
| Nop nop = new Nop(); |
| relativeOffset -= nop.getSize(); |
| instructions.add(nop); |
| } |
| assert relativeOffset != 0; |
| Instruction instruction = null; |
| if (branch.isZeroTest()) { |
| switch (getBranch().getType()) { |
| case EQ: |
| instruction = new IfEqz(register1, relativeOffset); |
| break; |
| case GE: |
| instruction = new IfGez(register1, relativeOffset); |
| break; |
| case GT: |
| instruction = new IfGtz(register1, relativeOffset); |
| break; |
| case LE: |
| instruction = new IfLez(register1, relativeOffset); |
| break; |
| case LT: |
| instruction = new IfLtz(register1, relativeOffset); |
| break; |
| case NE: |
| instruction = new IfNez(register1, relativeOffset); |
| break; |
| } |
| } else { |
| int register2 = builder.allocatedRegister(branch.inValues().get(1), branch.getNumber()); |
| switch (getBranch().getType()) { |
| case EQ: |
| instruction = new IfEq(register1, register2, relativeOffset); |
| break; |
| case GE: |
| instruction = new IfGe(register1, register2, relativeOffset); |
| break; |
| case GT: |
| instruction = new IfGt(register1, register2, relativeOffset); |
| break; |
| case LE: |
| instruction = new IfLe(register1, register2, relativeOffset); |
| break; |
| case LT: |
| instruction = new IfLt(register1, register2, relativeOffset); |
| break; |
| case NE: |
| instruction = new IfNe(register1, register2, relativeOffset); |
| break; |
| } |
| } |
| instruction.setOffset(getOffset()); |
| instructions.add(instruction); |
| } |
| |
| @Override |
| public int computeSize(DexBuilder builder) { |
| if (offsetOutOfRange(builder)) { |
| builder.needsIfRewriting(getBranch().getBlock()); |
| } |
| size = branchesToSelf(builder) ? 3 : 2; |
| return size; |
| } |
| |
| @Override |
| public int minSize() { |
| return 2; |
| } |
| |
| @Override |
| public int maxSize() { |
| return 3; |
| } |
| |
| @Override |
| public int getSize() { |
| return size; |
| } |
| } |
| |
| public static class MoveInfo extends Info { |
| |
| private int size = -1; |
| |
| public MoveInfo(Move move) { |
| super(move); |
| } |
| |
| private Move getMove() { |
| return (Move) getIR(); |
| } |
| |
| @Override |
| public int computeSize(DexBuilder builder) { |
| Move move = getMove(); |
| int srcRegister = builder.allocatedRegister(move.src(), move.getNumber()); |
| int destRegister = builder.allocatedRegister(move.dest(), move.getNumber()); |
| if (srcRegister == destRegister) { |
| size = 1; |
| } else if (srcRegister <= Constants.U4BIT_MAX && destRegister <= Constants.U4BIT_MAX) { |
| size = 1; |
| } else if (destRegister <= Constants.U8BIT_MAX) { |
| size = 2; |
| } else { |
| size = 3; |
| } |
| return size; |
| } |
| |
| @Override |
| public void addInstructions(DexBuilder builder, List<Instruction> instructions) { |
| Move move = getMove(); |
| int dest = builder.allocatedRegister(move.dest(), move.getNumber()); |
| int src = builder.allocatedRegister(move.src(), move.getNumber()); |
| Instruction instruction = null; |
| switch (size) { |
| case 1: |
| if (src == dest) { |
| instruction = new Nop(); |
| break; |
| } |
| switch (move.outType()) { |
| case SINGLE: |
| instruction = new com.android.tools.r8.code.Move(dest, src); |
| break; |
| case WIDE: |
| instruction = new MoveWide(dest, src); |
| break; |
| case OBJECT: |
| instruction = new MoveObject(dest, src); |
| break; |
| default: |
| throw new Unreachable("Unexpected type: " + move.outType()); |
| } |
| break; |
| case 2: |
| switch (move.outType()) { |
| case SINGLE: |
| instruction = new MoveFrom16(dest, src); |
| break; |
| case WIDE: |
| instruction = new MoveWideFrom16(dest, src); |
| break; |
| case OBJECT: |
| instruction = new MoveObjectFrom16(dest, src); |
| break; |
| default: |
| throw new Unreachable("Unexpected type: " + move.outType()); |
| } |
| break; |
| case 3: |
| switch (move.outType()) { |
| case SINGLE: |
| instruction = new Move16(dest, src); |
| break; |
| case WIDE: |
| instruction = new MoveWide16(dest, src); |
| break; |
| case OBJECT: |
| instruction = new MoveObject16(dest, src); |
| break; |
| default: |
| throw new Unreachable("Unexpected type: " + move.outType()); |
| } |
| break; |
| default: |
| throw new Unreachable("Unexpected size: " + size); |
| } |
| instruction.setOffset(getOffset()); |
| instructions.add(instruction); |
| } |
| |
| @Override |
| public int minSize() { |
| assert new Nop().getSize() == 1 && new com.android.tools.r8.code.Move(0, 0).getSize() == 1; |
| return 1; |
| } |
| |
| @Override |
| public int maxSize() { |
| assert new Move16(0, 0).getSize() == 3; |
| return 3; |
| } |
| |
| @Override |
| public int getSize() { |
| assert size > 0; |
| return size; |
| } |
| } |
| |
| // Return-type wrapper for try-related data. |
| private static class TryInfo { |
| |
| public final Try[] tries; |
| public final TryHandler[] handlers; |
| |
| public TryInfo(Try[] tries, TryHandler[] handlers) { |
| this.tries = tries; |
| this.handlers = handlers; |
| } |
| } |
| |
| // Helper class for coalescing ranges for try blocks. |
| private static class TryItem implements Comparable<TryItem> { |
| |
| public final CatchHandlers<BasicBlock> handlers; |
| public int start; |
| public int end; |
| |
| public TryItem(CatchHandlers<BasicBlock> handlers, int start, int end) { |
| this.handlers = handlers; |
| this.start = start; |
| this.end = end; |
| } |
| |
| @Override |
| public int compareTo(TryItem other) { |
| return Integer.compare(start, other.start); |
| } |
| } |
| |
| private static class SwitchPayloadInfo { |
| |
| public final Switch ir; |
| public final Format31t dex; |
| |
| public SwitchPayloadInfo(Switch ir, Format31t dex) { |
| this.ir = ir; |
| this.dex = dex; |
| } |
| } |
| |
| private static class FillArrayDataInfo { |
| |
| public final NewArrayFilledData ir; |
| public final FillArrayData dex; |
| |
| public FillArrayDataInfo(NewArrayFilledData ir, FillArrayData dex) { |
| this.ir = ir; |
| this.dex = dex; |
| } |
| } |
| } |
