| // Copyright (c) 2017, 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.ir.code.BasicBlock; |
| import com.android.tools.r8.ir.code.ConstNumber; |
| import com.android.tools.r8.ir.code.IRCode; |
| import com.android.tools.r8.ir.code.Instruction; |
| 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 it.unimi.dsi.fastutil.Hash.Strategy; |
| import it.unimi.dsi.fastutil.objects.Object2ObjectLinkedOpenCustomHashMap; |
| import it.unimi.dsi.fastutil.objects.Object2ObjectSortedMap.FastSortedEntrySet; |
| import java.util.ArrayList; |
| import java.util.List; |
| |
| /** |
| * Canonicalize constants. |
| */ |
| public class ConstantCanonicalizer { |
| |
| private static final int MAX_CANONICALIZED_CONSTANT = 15; |
| |
| public static void canonicalize(IRCode code) { |
| Object2ObjectLinkedOpenCustomHashMap<ConstNumber, List<Value>> valuesDefinedByConstant = |
| new Object2ObjectLinkedOpenCustomHashMap<>( |
| new Strategy<ConstNumber>() { |
| @Override |
| public int hashCode(ConstNumber constNumber) { |
| return Long.hashCode(constNumber.getRawValue()) + |
| 13 * constNumber.outType().hashCode(); |
| } |
| |
| @Override |
| public boolean equals(ConstNumber a, ConstNumber b) { |
| // Constants with local info must not be canonicalized and must be filtered. |
| assert a == null || !a.outValue().hasLocalInfo(); |
| assert b == null || !b.outValue().hasLocalInfo(); |
| return a != null && |
| b != null && |
| a.identicalNonValueNonPositionParts(b); |
| } |
| }); |
| |
| // Collect usages of constants that can be canonicalized. Constants that are used by invoke |
| // range are not be canonicalized to be compliant with the optimization splitrangeInvokeConstant |
| // that gives the register allocator more freedom in assigning register to ranged invokes |
| // which can greatly reduce the number of register needed (and thereby code size as well). Thus |
| // no need to do a transformation that should be removed later by another optimization. |
| for (BasicBlock block : code.blocks) { |
| InstructionListIterator it = block.listIterator(); |
| while (it.hasNext()) { |
| Instruction current = it.next(); |
| if (current.isConstNumber() && |
| !current.outValue().hasLocalInfo() && |
| !constantUsedByInvokeRange(current.asConstNumber())) { |
| List<Value> oldValuesDefinedByConstant = valuesDefinedByConstant.get(current); |
| if (oldValuesDefinedByConstant == null) { |
| oldValuesDefinedByConstant = new ArrayList<>(); |
| valuesDefinedByConstant.put(current.asConstNumber(), oldValuesDefinedByConstant); |
| } |
| oldValuesDefinedByConstant.add(current.outValue()); |
| } |
| } |
| } |
| |
| if (!valuesDefinedByConstant.isEmpty()) { |
| FastSortedEntrySet<ConstNumber, List<Value>> entries = |
| valuesDefinedByConstant.object2ObjectEntrySet(); |
| // Sort the most frequently used constant first and exclude constant use only one time, such |
| // as the {@code MAX_CANONICALIZED_CONSTANT} will canonicalized into the entry block. |
| entries.stream() |
| .filter(a -> a.getValue().size() > 1) |
| .sorted((a, b) -> Integer.compare(b.getValue().size(), a.getValue().size())) |
| .limit(MAX_CANONICALIZED_CONSTANT) |
| .forEach((entry) -> { |
| ConstNumber canonicalizedConstant = entry.getKey().asConstNumber(); |
| ConstNumber newConst = ConstNumber.copyOf(code, canonicalizedConstant); |
| insertCanonicalizedConstant(code, newConst); |
| newConst.setPosition(Position.none()); |
| for (Value outValue : entry.getValue()) { |
| outValue.replaceUsers(newConst.outValue()); |
| } |
| }); |
| } |
| |
| assert code.isConsistentSSA(); |
| } |
| |
| private static void insertCanonicalizedConstant (IRCode code, ConstNumber canonicalizedConstant) { |
| BasicBlock entryBlock = code.blocks.get(0); |
| // Insert the constant instruction at the start of the block right after the argument |
| // instructions. It is important that the const instruction is put before any instruction |
| // that can throw exceptions (since the value could be used on the exceptional edge). |
| InstructionListIterator it = entryBlock.listIterator(); |
| while (it.hasNext()) { |
| if (!it.next().isArgument()) { |
| it.previous(); |
| break; |
| } |
| } |
| it.add(canonicalizedConstant); |
| } |
| |
| private static boolean constantUsedByInvokeRange(ConstNumber constant) { |
| for (Instruction user : constant.outValue().uniqueUsers()) { |
| if (user.isInvoke() && user.asInvoke().requiredArgumentRegisters() > 5) { |
| return true; |
| } |
| } |
| return false; |
| } |
| } |