| // 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.optimize; |
| |
| import com.android.tools.r8.graph.DebugLocalInfo; |
| import com.android.tools.r8.ir.code.BasicBlock; |
| import com.android.tools.r8.ir.code.ConstNumber; |
| import com.android.tools.r8.ir.code.DebugLocalsChange; |
| import com.android.tools.r8.ir.code.Goto; |
| 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.InstructionListIterator; |
| import com.android.tools.r8.ir.code.Position; |
| import com.android.tools.r8.ir.code.Value; |
| import com.android.tools.r8.ir.regalloc.LinearScanRegisterAllocator; |
| import com.android.tools.r8.ir.regalloc.LiveIntervals; |
| import com.android.tools.r8.ir.regalloc.RegisterAllocator; |
| import com.google.common.base.Equivalence.Wrapper; |
| import com.google.common.collect.Sets; |
| import it.unimi.dsi.fastutil.ints.Int2ReferenceMap; |
| import it.unimi.dsi.fastutil.ints.Int2ReferenceOpenHashMap; |
| import java.util.ArrayList; |
| import java.util.Collection; |
| import java.util.HashMap; |
| import java.util.IdentityHashMap; |
| import java.util.LinkedList; |
| import java.util.List; |
| import java.util.ListIterator; |
| import java.util.Map; |
| import java.util.Objects; |
| import java.util.Set; |
| |
| public class PeepholeOptimizer { |
| /** |
| * Perform optimizations of the code with register assignments provided by the register allocator. |
| */ |
| public static void optimize(IRCode code, LinearScanRegisterAllocator allocator) { |
| removeIdenticalPredecessorBlocks(code, allocator); |
| removeRedundantInstructions(code, allocator); |
| shareIdenticalBlockPrefix(code, allocator); |
| shareIdenticalBlockSuffix(code, allocator, 0); |
| assert code.isConsistentGraph(); |
| } |
| |
| /** Identify common prefixes in successor blocks and share them. */ |
| private static void shareIdenticalBlockPrefix(IRCode code, RegisterAllocator allocator) { |
| InstructionEquivalence equivalence = new InstructionEquivalence(allocator); |
| Set<BasicBlock> blocksToBeRemoved = Sets.newIdentityHashSet(); |
| for (BasicBlock block : code.blocks) { |
| shareIdenticalBlockPrefixFromNormalSuccessors( |
| block, allocator, blocksToBeRemoved, equivalence); |
| } |
| code.blocks.removeAll(blocksToBeRemoved); |
| } |
| |
| private static void shareIdenticalBlockPrefixFromNormalSuccessors( |
| BasicBlock block, |
| RegisterAllocator allocator, |
| Set<BasicBlock> blocksToBeRemoved, |
| InstructionEquivalence equivalence) { |
| if (blocksToBeRemoved.contains(block)) { |
| // This block has already been removed entirely. |
| return; |
| } |
| |
| if (!mayShareIdenticalBlockPrefix(block)) { |
| // Not eligible. |
| return; |
| } |
| |
| // Share instructions from the normal successors one-by-one. |
| List<BasicBlock> normalSuccessors = block.getNormalSuccessors(); |
| while (true) { |
| BasicBlock firstNormalSuccessor = normalSuccessors.get(0); |
| |
| // Check if all instructions were already removed from the normal successors. |
| for (BasicBlock normalSuccessor : normalSuccessors) { |
| if (normalSuccessor.isEmpty()) { |
| assert blocksToBeRemoved.containsAll(normalSuccessors); |
| return; |
| } |
| } |
| |
| // If the first instruction in all successors is not the same, we cannot merge them into the |
| // predecessor. |
| Instruction instruction = firstNormalSuccessor.entry(); |
| for (int i = 1; i < normalSuccessors.size(); i++) { |
| BasicBlock otherNormalSuccessor = normalSuccessors.get(i); |
| Instruction otherInstruction = otherNormalSuccessor.entry(); |
| if (!equivalence.doEquivalent(instruction, otherInstruction)) { |
| return; |
| } |
| } |
| |
| if (instruction.instructionTypeCanThrow()) { |
| // Each block with one or more catch handlers may have at most one throwing instruction. |
| if (block.hasCatchHandlers()) { |
| return; |
| } |
| |
| // If the instruction can throw and one of the normal successor blocks has a catch handler, |
| // then we cannot merge the instruction into the predecessor, since this would change the |
| // exceptional control flow. |
| for (BasicBlock normalSuccessor : normalSuccessors) { |
| if (normalSuccessor.hasCatchHandlers()) { |
| return; |
| } |
| } |
| } |
| |
| // Check for commutativity (semantics). If the instruction writes to a register, then we |
| // need to make sure that the instruction commutes with the last instruction in the |
| // predecessor. Consider the following example. |
| // |
| // <Block A> |
| // if-eqz r0 then goto Block B else goto Block C |
| // / \ |
| // <Block B> <Block C> |
| // const r0, 1 const r0, 1 |
| // ... ... |
| // |
| // In the example, it is not possible to change the order of "if-eqz r0" and |
| // "const r0, 1" without changing the semantics. |
| if (instruction.outValue() != null && instruction.outValue().needsRegister()) { |
| int destinationRegister = |
| allocator.getRegisterForValue(instruction.outValue(), instruction.getNumber()); |
| boolean commutative = |
| block.exit().inValues().stream() |
| .allMatch( |
| inValue -> { |
| int operandRegister = |
| allocator.getRegisterForValue(inValue, block.exit().getNumber()); |
| for (int i = 0; i < instruction.outValue().requiredRegisters(); i++) { |
| for (int j = 0; j < inValue.requiredRegisters(); j++) { |
| if (destinationRegister + i == operandRegister + j) { |
| // Overlap detected, the two instructions do not commute. |
| return false; |
| } |
| } |
| } |
| return true; |
| }); |
| if (!commutative) { |
| return; |
| } |
| } |
| |
| // Check for commutativity (debug info). |
| if (!instruction.getPosition().equals(block.exit().getPosition()) |
| && !(block.exit().getPosition().isNone() && !block.exit().getDebugValues().isEmpty())) { |
| return; |
| } |
| |
| // Remove the instruction from the normal successors. |
| for (BasicBlock normalSuccessor : normalSuccessors) { |
| normalSuccessor.getInstructions().removeFirst(); |
| } |
| |
| // Move the instruction into the predecessor. |
| if (instruction.isJumpInstruction()) { |
| // Replace jump instruction in predecessor with the jump instruction from the normal |
| // successors. |
| LinkedList<Instruction> instructions = block.getInstructions(); |
| instructions.removeLast(); |
| instructions.add(instruction); |
| instruction.setBlock(block); |
| |
| // Take a copy of the old normal successors before performing a destructive update. |
| List<BasicBlock> oldNormalSuccessors = new ArrayList<>(normalSuccessors); |
| |
| // Update successors of predecessor block. |
| block.detachAllSuccessors(); |
| for (BasicBlock newNormalSuccessor : firstNormalSuccessor.getNormalSuccessors()) { |
| block.link(newNormalSuccessor); |
| } |
| |
| // Detach the previous normal successors from the rest of the graph. |
| for (BasicBlock oldNormalSuccessor : oldNormalSuccessors) { |
| oldNormalSuccessor.detachAllSuccessors(); |
| } |
| |
| // Record that the previous normal successors should be removed entirely. |
| blocksToBeRemoved.addAll(oldNormalSuccessors); |
| |
| if (!mayShareIdenticalBlockPrefix(block)) { |
| return; |
| } |
| } else { |
| // Insert instruction before the jump instruction in the predecessor. |
| block.getInstructions().listIterator(block.getInstructions().size() - 1).add(instruction); |
| instruction.setBlock(block); |
| |
| // Update locals-at-entry if needed. |
| if (instruction.isDebugLocalsChange()) { |
| DebugLocalsChange localsChange = instruction.asDebugLocalsChange(); |
| for (BasicBlock normalSuccessor : normalSuccessors) { |
| localsChange.apply(normalSuccessor.getLocalsAtEntry()); |
| } |
| } |
| } |
| } |
| } |
| |
| private static boolean mayShareIdenticalBlockPrefix(BasicBlock block) { |
| List<BasicBlock> normalSuccessors = block.getNormalSuccessors(); |
| if (normalSuccessors.size() <= 1) { |
| // Nothing to share. |
| return false; |
| } |
| |
| // Ensure that the current block is on all paths to the successor blocks. |
| for (BasicBlock normalSuccessor : normalSuccessors) { |
| if (normalSuccessor.getPredecessors().size() != 1) { |
| return false; |
| } |
| } |
| |
| // Only try to share instructions if the normal successors have the same locals state on entry. |
| BasicBlock firstNormalSuccessor = normalSuccessors.get(0); |
| for (int i = 1; i < normalSuccessors.size(); i++) { |
| BasicBlock otherNormalSuccessor = normalSuccessors.get(i); |
| if (!Objects.equals( |
| firstNormalSuccessor.getLocalsAtEntry(), otherNormalSuccessor.getLocalsAtEntry())) { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| /** Identify common suffixes in predecessor blocks and share them. */ |
| public static void shareIdenticalBlockSuffix( |
| IRCode code, RegisterAllocator allocator, int overhead) { |
| Collection<BasicBlock> blocks = code.blocks; |
| BasicBlock normalExit = null; |
| List<BasicBlock> normalExits = code.computeNormalExitBlocks(); |
| if (normalExits.size() > 1) { |
| normalExit = new BasicBlock(); |
| normalExit.getMutablePredecessors().addAll(normalExits); |
| blocks = new ArrayList<>(code.blocks); |
| blocks.add(normalExit); |
| } |
| do { |
| Map<BasicBlock, BasicBlock> newBlocks = new IdentityHashMap<>(); |
| for (BasicBlock block : blocks) { |
| InstructionEquivalence equivalence = new InstructionEquivalence(allocator); |
| // Group interesting predecessor blocks by their last instruction. |
| Map<Wrapper<Instruction>, List<BasicBlock>> lastInstructionToBlocks = new HashMap<>(); |
| for (BasicBlock pred : block.getPredecessors()) { |
| // Only deal with predecessors with one successor. This way we can move throwing |
| // instructions as well since there are no handlers (or the handler is the same as the |
| // normal control-flow block). Alternatively, we could move only non-throwing instructions |
| // and allow both a goto edge and exception edges when the target does not start with a |
| // MoveException instruction. However, that would require us to require rewriting of |
| // catch handlers as well. |
| if (pred.exit().isGoto() |
| && pred.getSuccessors().size() == 1 |
| && pred.getInstructions().size() > 1) { |
| List<Instruction> instructions = pred.getInstructions(); |
| Instruction lastInstruction = instructions.get(instructions.size() - 2); |
| List<BasicBlock> value = lastInstructionToBlocks.computeIfAbsent( |
| equivalence.wrap(lastInstruction), (k) -> new ArrayList<>()); |
| value.add(pred); |
| } else if (pred.exit().isReturn() |
| && pred.getSuccessors().isEmpty() |
| && pred.getInstructions().size() > 2) { |
| Instruction lastInstruction = pred.exit(); |
| List<BasicBlock> value = |
| lastInstructionToBlocks.computeIfAbsent( |
| equivalence.wrap(lastInstruction), (k) -> new ArrayList<>()); |
| value.add(pred); |
| } |
| } |
| // For each group of predecessors of size 2 or more, find the largest common suffix and |
| // move that to a separate block. |
| for (List<BasicBlock> predsWithSameLastInstruction : lastInstructionToBlocks.values()) { |
| if (predsWithSameLastInstruction.size() < 2) { |
| continue; |
| } |
| BasicBlock firstPred = predsWithSameLastInstruction.get(0); |
| int commonSuffixSize = firstPred.getInstructions().size(); |
| for (int i = 1; i < predsWithSameLastInstruction.size(); i++) { |
| BasicBlock pred = predsWithSameLastInstruction.get(i); |
| assert pred.exit().isGoto() || pred.exit().isReturn(); |
| commonSuffixSize = |
| Math.min(commonSuffixSize, sharedSuffixSize(firstPred, pred, allocator)); |
| } |
| |
| int sizeDelta = overhead - (predsWithSameLastInstruction.size() - 1) * commonSuffixSize; |
| |
| // Don't share a suffix that is just a single goto or return instruction. |
| if (commonSuffixSize <= 1 || sizeDelta >= 0) { |
| continue; |
| } |
| BasicBlock newBlock = |
| createAndInsertBlockForSuffix( |
| code.getNextBlockNumber(), |
| commonSuffixSize, |
| predsWithSameLastInstruction, |
| block == normalExit ? null : block, |
| allocator); |
| newBlocks.put(predsWithSameLastInstruction.get(0), newBlock); |
| } |
| } |
| ListIterator<BasicBlock> blockIterator = code.listIterator(); |
| while (blockIterator.hasNext()) { |
| BasicBlock block = blockIterator.next(); |
| if (newBlocks.containsKey(block)) { |
| blockIterator.add(newBlocks.get(block)); |
| } |
| } |
| // Go through all the newly introduced blocks to find more common suffixes to share. |
| blocks = newBlocks.values(); |
| } while (!blocks.isEmpty()); |
| } |
| |
| private static BasicBlock createAndInsertBlockForSuffix( |
| int blockNumber, |
| int suffixSize, |
| List<BasicBlock> preds, |
| BasicBlock successorBlock, |
| RegisterAllocator allocator) { |
| BasicBlock first = preds.get(0); |
| assert (successorBlock != null && first.exit().isGoto()) |
| || (successorBlock == null && first.exit().isReturn()); |
| BasicBlock newBlock = new BasicBlock(); |
| newBlock.setNumber(blockNumber); |
| InstructionIterator from = first.iterator(first.getInstructions().size()); |
| Int2ReferenceMap<DebugLocalInfo> newBlockEntryLocals = null; |
| if (first.getLocalsAtEntry() != null) { |
| newBlockEntryLocals = new Int2ReferenceOpenHashMap<>(first.getLocalsAtEntry()); |
| int prefixSize = first.getInstructions().size() - suffixSize; |
| InstructionIterator it = first.iterator(); |
| for (int i = 0; i < prefixSize; i++) { |
| Instruction instruction = it.next(); |
| if (instruction.isDebugLocalsChange()) { |
| instruction.asDebugLocalsChange().apply(newBlockEntryLocals); |
| } |
| } |
| } |
| |
| allocator.addNewBlockToShareIdenticalSuffix(newBlock, suffixSize, preds); |
| |
| boolean movedThrowingInstruction = false; |
| for (int i = 0; i < suffixSize; i++) { |
| Instruction instruction = from.previous(); |
| movedThrowingInstruction = movedThrowingInstruction || instruction.instructionTypeCanThrow(); |
| newBlock.getInstructions().addFirst(instruction); |
| instruction.setBlock(newBlock); |
| } |
| if (movedThrowingInstruction && first.hasCatchHandlers()) { |
| newBlock.transferCatchHandlers(first); |
| } |
| for (BasicBlock pred : preds) { |
| Position lastPosition = pred.getPosition(); |
| LinkedList<Instruction> instructions = pred.getInstructions(); |
| for (int i = 0; i < suffixSize; i++) { |
| instructions.removeLast(); |
| } |
| for (Instruction instruction : pred.getInstructions()) { |
| if (instruction.getPosition().isSome()) { |
| lastPosition = instruction.getPosition(); |
| } |
| } |
| Goto jump = new Goto(); |
| jump.setBlock(pred); |
| jump.setPosition(lastPosition); |
| instructions.add(jump); |
| newBlock.getMutablePredecessors().add(pred); |
| if (successorBlock != null) { |
| pred.replaceSuccessor(successorBlock, newBlock); |
| successorBlock.getMutablePredecessors().remove(pred); |
| } else { |
| pred.getMutableSuccessors().add(newBlock); |
| } |
| if (movedThrowingInstruction) { |
| pred.clearCatchHandlers(); |
| } |
| } |
| newBlock.close(null); |
| if (newBlockEntryLocals != null) { |
| newBlock.setLocalsAtEntry(newBlockEntryLocals); |
| } |
| if (successorBlock != null) { |
| newBlock.link(successorBlock); |
| } |
| return newBlock; |
| } |
| |
| private static Int2ReferenceMap<DebugLocalInfo> localsAtBlockExit(BasicBlock block) { |
| if (block.getLocalsAtEntry() == null) { |
| return null; |
| } |
| Int2ReferenceMap<DebugLocalInfo> locals = |
| new Int2ReferenceOpenHashMap<>(block.getLocalsAtEntry()); |
| for (Instruction instruction : block.getInstructions()) { |
| if (instruction.isDebugLocalsChange()) { |
| instruction.asDebugLocalsChange().apply(locals); |
| } |
| } |
| return locals; |
| } |
| |
| private static int sharedSuffixSize( |
| BasicBlock block0, BasicBlock block1, RegisterAllocator allocator) { |
| assert block0.exit().isGoto() || block0.exit().isReturn(); |
| // If the blocks do not agree on locals at exit then they don't have any shared suffix. |
| if (!Objects.equals(localsAtBlockExit(block0), localsAtBlockExit(block1))) { |
| return 0; |
| } |
| InstructionIterator it0 = block0.iterator(block0.getInstructions().size()); |
| InstructionIterator it1 = block1.iterator(block1.getInstructions().size()); |
| int suffixSize = 0; |
| while (it0.hasPrevious() && it1.hasPrevious()) { |
| Instruction i0 = it0.previous(); |
| Instruction i1 = it1.previous(); |
| if (!i0.identicalAfterRegisterAllocation(i1, allocator)) { |
| return suffixSize; |
| } |
| suffixSize++; |
| } |
| return suffixSize; |
| } |
| |
| /** |
| * If two predecessors have the same code and successors. Replace one of them with an empty block |
| * with a goto to the other. |
| */ |
| public static void removeIdenticalPredecessorBlocks(IRCode code, RegisterAllocator allocator) { |
| BasicBlockInstructionsEquivalence equivalence = |
| new BasicBlockInstructionsEquivalence(code, allocator); |
| // Locate one block at a time that has identical predecessors. Rewrite those predecessors and |
| // then start over. Restarting when one blocks predecessors have been rewritten simplifies |
| // the rewriting and reduces the size of the data structures. |
| boolean changed; |
| do { |
| changed = false; |
| for (BasicBlock block : code.blocks) { |
| Map<Wrapper<BasicBlock>, Integer> blockToIndex = new HashMap<>(); |
| for (int predIndex = 0; predIndex < block.getPredecessors().size(); predIndex++) { |
| BasicBlock pred = block.getPredecessors().get(predIndex); |
| if (pred.getInstructions().size() == 1) { |
| continue; |
| } |
| Wrapper<BasicBlock> wrapper = equivalence.wrap(pred); |
| if (blockToIndex.containsKey(wrapper)) { |
| changed = true; |
| int otherPredIndex = blockToIndex.get(wrapper); |
| BasicBlock otherPred = block.getPredecessors().get(otherPredIndex); |
| assert !allocator.options().debug |
| || Objects.equals(pred.getPosition(), otherPred.getPosition()); |
| allocator.mergeBlocks(otherPred, pred); |
| pred.clearCatchHandlers(); |
| pred.getInstructions().clear(); |
| equivalence.clearComputedHash(pred); |
| for (BasicBlock succ : pred.getSuccessors()) { |
| succ.removePredecessor(pred, null); |
| } |
| pred.getMutableSuccessors().clear(); |
| pred.getMutableSuccessors().add(otherPred); |
| assert !otherPred.getPredecessors().contains(pred); |
| otherPred.getMutablePredecessors().add(pred); |
| Goto exit = new Goto(); |
| exit.setBlock(pred); |
| exit.setPosition(otherPred.getPosition()); |
| pred.getInstructions().add(exit); |
| } else { |
| blockToIndex.put(wrapper, predIndex); |
| } |
| } |
| } |
| } while (changed); |
| } |
| |
| /** |
| * Remove redundant instructions from the code. |
| * |
| * <p>Currently removes move instructions with the same src and target register and const |
| * instructions where the constant is known to be in the register already. |
| * |
| * @param code the code from which to remove redundant instruction |
| * @param allocator the register allocator providing registers for values |
| */ |
| private static void removeRedundantInstructions( |
| IRCode code, LinearScanRegisterAllocator allocator) { |
| for (BasicBlock block : code.blocks) { |
| // Mapping from register number to const number instructions for this basic block. |
| // Used to remove redundant const instructions that reloads the same constant into |
| // the same register. |
| Map<Integer, ConstNumber> registerToNumber = new HashMap<>(); |
| MoveEliminator moveEliminator = new MoveEliminator(allocator); |
| InstructionListIterator iterator = block.listIterator(code); |
| while (iterator.hasNext()) { |
| Instruction current = iterator.next(); |
| if (moveEliminator.shouldBeEliminated(current)) { |
| iterator.removeInstructionIgnoreOutValue(); |
| } else if (current.outValue() != null && current.outValue().needsRegister()) { |
| Value outValue = current.outValue(); |
| int instructionNumber = current.getNumber(); |
| if (outValue.isConstant() && current.isConstNumber()) { |
| if (constantSpilledAtDefinition(current.asConstNumber())) { |
| // Remove constant instructions that are spilled at their definition and are |
| // therefore unused. |
| iterator.removeInstructionIgnoreOutValue(); |
| continue; |
| } |
| int outRegister = allocator.getRegisterForValue(outValue, instructionNumber); |
| ConstNumber numberInRegister = registerToNumber.get(outRegister); |
| if (numberInRegister != null |
| && numberInRegister.identicalNonValueNonPositionParts(current)) { |
| // This instruction is not needed, the same constant is already in this register. |
| // We don't consider the positions of the two (non-throwing) instructions. |
| iterator.removeInstructionIgnoreOutValue(); |
| } else { |
| // Insert the current constant in the mapping. Make sure to clobber the second |
| // register if wide and register-1 if that defines a wide value. |
| registerToNumber.put(outRegister, current.asConstNumber()); |
| if (current.outType().isWide()) { |
| registerToNumber.remove(outRegister + 1); |
| } |
| removeWideConstantCovering(registerToNumber, outRegister); |
| } |
| } else { |
| // This instruction writes registers with a non-constant value. Remove the registers |
| // from the mapping. |
| int outRegister = allocator.getRegisterForValue(outValue, instructionNumber); |
| for (int i = 0; i < outValue.requiredRegisters(); i++) { |
| registerToNumber.remove(outRegister + i); |
| } |
| // Check if the first register written is the second part of a wide value. If so |
| // the wide value is no longer active. |
| removeWideConstantCovering(registerToNumber, outRegister); |
| } |
| } |
| } |
| } |
| } |
| |
| private static void removeWideConstantCovering( |
| Map<Integer, ConstNumber> registerToNumber, int register) { |
| ConstNumber number = registerToNumber.get(register - 1); |
| if (number != null && number.outType().isWide()) { |
| registerToNumber.remove(register - 1); |
| } |
| } |
| |
| private static boolean constantSpilledAtDefinition(ConstNumber constNumber) { |
| if (constNumber.outValue().isFixedRegisterValue()) { |
| return false; |
| } |
| LiveIntervals definitionIntervals = |
| constNumber.outValue().getLiveIntervals().getSplitCovering(constNumber.getNumber()); |
| return definitionIntervals.isSpilledAndRematerializable(); |
| } |
| } |