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);
