Canonicalize constants - Constants that have debug information or that are used by invoke-range are not canonicalized. - It slightly decrease dex size on GMSCore V10 in release mode (3.5k). Bug: 70659883 Change-Id: Ib088448170abe9e8bc6a92a555c7117d64afb6eb
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java b/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java index b392308..c8ab5b9 100644 --- a/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java +++ b/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
@@ -90,8 +90,6 @@ import it.unimi.dsi.fastutil.ints.IntIterator; import it.unimi.dsi.fastutil.ints.IntList; import it.unimi.dsi.fastutil.ints.IntSet; -import it.unimi.dsi.fastutil.longs.Long2ObjectArrayMap; -import it.unimi.dsi.fastutil.longs.Long2ObjectMap; import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; @@ -263,13 +261,6 @@ private BasicBlock currentBlock = null; - // Mappings for canonicalizing constants of a given type at IR construction time. - private Long2ObjectMap<ConstNumber> intConstants = new Long2ObjectArrayMap<>(); - private Long2ObjectMap<ConstNumber> longConstants = new Long2ObjectArrayMap<>(); - private Long2ObjectMap<ConstNumber> floatConstants = new Long2ObjectArrayMap<>(); - private Long2ObjectMap<ConstNumber> doubleConstants = new Long2ObjectArrayMap<>(); - private Long2ObjectMap<ConstNumber> nullConstants = new Long2ObjectArrayMap<>(); - private List<BasicBlock.Pair> needGotoToCatchBlocks = new ArrayList<>(); final private ValueNumberGenerator valueNumberGenerator; @@ -411,7 +402,6 @@ // Clear the code so we don't build multiple times. source.clear(); - clearCanonicalizationMaps(); source = null; for (BasicBlock block : blocks) { @@ -459,14 +449,6 @@ return hasDebugPositions; } - private void clearCanonicalizationMaps() { - intConstants = null; - longConstants = null; - floatConstants = null; - doubleConstants = null; - nullConstants = null; - } - private boolean verifyFilledPredecessors() { for (BasicBlock block : blocks) { assert verifyFilledPredecessors(block); @@ -788,40 +770,24 @@ add(instruction); } - // TODO(ager): Does art support changing the value of locals during debugging? If so, we need - // to disable constant canonicalization in debug builds to make sure we have separate values - // for separate locals. - private void canonicalizeAndAddConst( - ValueType type, int dest, long value, Long2ObjectMap<ConstNumber> table) { - ConstNumber existing = table.get(value); - if (existing != null) { - currentBlock.writeCurrentDefinition(dest, existing.outValue(), ThrowingInfo.NO_THROW); - } else { - Value out = writeRegister(dest, type, ThrowingInfo.NO_THROW); - ConstNumber instruction = new ConstNumber(out, value); - insertCanonicalizedConstant(instruction); - table.put(value, instruction); - } - } - public void addLongConst(int dest, long value) { - canonicalizeAndAddConst(ValueType.LONG, dest, value, longConstants); + add(new ConstNumber(writeRegister(dest, ValueType.LONG, ThrowingInfo.NO_THROW), value)); } public void addDoubleConst(int dest, long value) { - canonicalizeAndAddConst(ValueType.DOUBLE, dest, value, doubleConstants); + add(new ConstNumber(writeRegister(dest, ValueType.DOUBLE, ThrowingInfo.NO_THROW), value)); } public void addIntConst(int dest, long value) { - canonicalizeAndAddConst(ValueType.INT, dest, value, intConstants); + add(new ConstNumber(writeRegister(dest, ValueType.INT, ThrowingInfo.NO_THROW), value)); } public void addFloatConst(int dest, long value) { - canonicalizeAndAddConst(ValueType.FLOAT, dest, value, floatConstants); + add(new ConstNumber(writeRegister(dest, ValueType.FLOAT, ThrowingInfo.NO_THROW), value)); } public void addNullConst(int dest) { - canonicalizeAndAddConst(ValueType.OBJECT, dest, 0L, nullConstants); + add(new ConstNumber(writeRegister(dest, ValueType.OBJECT, ThrowingInfo.NO_THROW), 0L)); } public void addConstClass(int dest, DexType type) { @@ -1637,12 +1603,10 @@ } public Value readIntLiteral(long constant) { - return intConstants.computeIfAbsent(constant, (c) -> { - Value value = new Value(valueNumberGenerator.next(), ValueType.INT, null); - ConstNumber number = new ConstNumber(value, constant); - insertCanonicalizedConstant(number); - return number; - }).outValue(); + Value value = new Value(valueNumberGenerator.next(), ValueType.INT, null); + ConstNumber number = new ConstNumber(value, constant); + add(number); + return number.outValue(); } // This special write register is needed when changing the scoping of a local variable. @@ -2024,25 +1988,5 @@ } return builder.toString(); } - - private void insertCanonicalizedConstant(ConstNumber number) { - BasicBlock entryBlock = blocks.get(0); - if (currentBlock != entryBlock) { - // 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(number); - number.setPosition(Position.none()); - } else { - add(number); - } - } }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java index 42a0a58..0899a84 100644 --- a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java +++ b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
@@ -27,6 +27,7 @@ import com.android.tools.r8.ir.desugar.LambdaRewriter; import com.android.tools.r8.ir.desugar.StringConcatRewriter; import com.android.tools.r8.ir.optimize.CodeRewriter; +import com.android.tools.r8.ir.optimize.ConstantCanonicalizer; import com.android.tools.r8.ir.optimize.DeadCodeRemover; import com.android.tools.r8.ir.optimize.Inliner; import com.android.tools.r8.ir.optimize.Inliner.Constraint; @@ -601,6 +602,7 @@ assert code.isConsistentSSA(); } + ConstantCanonicalizer.canonicalize(code); codeRewriter.useDedicatedConstantForLitInstruction(code); codeRewriter.shortenLiveRanges(code); codeRewriter.identifyReturnsArgument(method, code, feedback);
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/ConstantCanonicalizer.java b/src/main/java/com/android/tools/r8/ir/optimize/ConstantCanonicalizer.java new file mode 100644 index 0000000..7a6a846 --- /dev/null +++ b/src/main/java/com/android/tools/r8/ir/optimize/ConstantCanonicalizer.java
@@ -0,0 +1,115 @@ +// 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; + } +}
diff --git a/src/test/java/com/android/tools/r8/rewrite/switches/SwitchRewritingJarTest.java b/src/test/java/com/android/tools/r8/rewrite/switches/SwitchRewritingJarTest.java index 33de2fc..ae88c12 100644 --- a/src/test/java/com/android/tools/r8/rewrite/switches/SwitchRewritingJarTest.java +++ b/src/test/java/com/android/tools/r8/rewrite/switches/SwitchRewritingJarTest.java
@@ -136,7 +136,11 @@ assertTrue(code.instructions[0] instanceof PackedSwitch); } else { if (key1 == 0) { - assertTrue(code.instructions[0] instanceof IfEqz); + if (key2 == 3) { + assertTrue(code.instructions[1] instanceof IfEqz); + } else { + assertTrue(code.instructions[0] instanceof IfEqz); + } } else { // Const instruction before if. assertTrue(code.instructions[1] instanceof IfEq);