Further improve lowering constants for binop/lit8 and binop/lit16
* Don't explicitly number the instructions
* Cache negative path checks between basic blocks
This brings the compilation time of the supplied repro down to 29s (13s
seconds for d8). These numbers are from a P920, and the user time is
4m40s and 2m40s respectively.
On the supplied repro the d8 size saving is 342 bytes of dex when the
binop/2addr check is included (compressed it actually grown with 1837 bytes)
Bug: 145052564
Change-Id: I4c6dcd47474e17effb733c5eecaf9cd0109cb732
diff --git a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
index b2273e9..d71b495 100644
--- a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
+++ b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
@@ -559,30 +559,13 @@
}
public int numberInstructions(int nextInstructionNumber) {
- return numberInstructions(nextInstructionNumber, INSTRUCTION_NUMBER_DELTA);
- }
-
- public int numberInstructions(int nextInstructionNumber, int increment) {
for (Instruction instruction : instructions) {
instruction.setNumber(nextInstructionNumber);
- nextInstructionNumber += increment;
+ nextInstructionNumber += INSTRUCTION_NUMBER_DELTA;
}
return nextInstructionNumber;
}
- public void clearInstructionNumbers() {
- for (Instruction instruction : instructions) {
- instruction.clearNumber();
- }
- }
-
- public boolean hasNoInstructionNumbers() {
- for (Instruction instruction : instructions) {
- assert instruction.getNumber() == -1;
- }
- return true;
- }
-
public LinkedList<Instruction> getInstructions() {
return instructions;
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/IRCode.java b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
index 6a130a1..1a34adf 100644
--- a/src/main/java/com/android/tools/r8/ir/code/IRCode.java
+++ b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
@@ -991,25 +991,6 @@
return blocks;
}
- public void numberInstructionsPerBlock() {
- for (BasicBlock block : blocks) {
- block.numberInstructions(0, 1);
- }
- }
-
- public void clearInstructionNumbers() {
- for (BasicBlock block : blocks) {
- block.clearInstructionNumbers();
- }
- }
-
- public boolean hasNoInstructionNumbers() {
- for (BasicBlock block : blocks) {
- assert block.hasNoInstructionNumbers();
- }
- return true;
- }
-
public int numberRemainingInstructions() {
for (Instruction instruction : instructions()) {
if (instruction.getNumber() == -1) {
diff --git a/src/main/java/com/android/tools/r8/ir/code/Instruction.java b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
index 6893464..8deda3f 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Instruction.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
@@ -268,6 +268,7 @@
/**
* Returns the basic block containing this instruction.
*/
+ @Override
public BasicBlock getBlock() {
assert block != null;
return block;
diff --git a/src/main/java/com/android/tools/r8/ir/code/InstructionOrPhi.java b/src/main/java/com/android/tools/r8/ir/code/InstructionOrPhi.java
index e9a5347..144bbdb 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InstructionOrPhi.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InstructionOrPhi.java
@@ -21,4 +21,6 @@
default Phi asPhi() {
return null;
}
+
+ BasicBlock getBlock();
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/Phi.java b/src/main/java/com/android/tools/r8/ir/code/Phi.java
index 3252d67..2f0911d 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Phi.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Phi.java
@@ -67,6 +67,7 @@
return this;
}
+ @Override
public BasicBlock getBlock() {
return block;
}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
index 326c17b..3a78425 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
@@ -51,6 +51,7 @@
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.InstructionOrPhi;
import com.android.tools.r8.ir.code.IntSwitch;
import com.android.tools.r8.ir.code.Invoke;
import com.android.tools.r8.ir.code.InvokeDirect;
@@ -1646,8 +1647,6 @@
return;
}
- code.numberInstructionsPerBlock();
-
for (BasicBlock block : code.blocks) {
InstructionListIterator instructionIterator = block.listIterator(code);
// Collect all the non constant in values for binop/lit8 or binop/lit16 instructions.
@@ -1669,26 +1668,32 @@
Reference2IntMap<Value> lastUseOfBinopsWithLit8OrLit16NonConstantValues =
new Reference2IntOpenHashMap<>();
lastUseOfBinopsWithLit8OrLit16NonConstantValues.defaultReturnValue(-1);
+ int currentInstructionNumber = block.getInstructions().size();
while (instructionIterator.hasPrevious()) {
Instruction currentInstruction = instructionIterator.previous();
- for (Value value : Iterables.concat(currentInstruction.inValues(), currentInstruction.getDebugValues())) {
+ currentInstructionNumber--;
+ for (Value value :
+ Iterables.concat(currentInstruction.inValues(), currentInstruction.getDebugValues())) {
if (!binopsWithLit8OrLit16NonConstantValues.contains(value)) {
continue;
}
if (!lastUseOfBinopsWithLit8OrLit16NonConstantValues.containsKey(value)) {
- lastUseOfBinopsWithLit8OrLit16NonConstantValues.put(
- value, currentInstruction.getNumber());
+ lastUseOfBinopsWithLit8OrLit16NonConstantValues.put(value, currentInstructionNumber);
}
}
}
// Do the transformation except if the binop can use the binop/2addr format.
+ currentInstructionNumber--;
+ assert currentInstructionNumber == -1;
while (instructionIterator.hasNext()) {
Instruction currentInstruction = instructionIterator.next();
+ currentInstructionNumber++;
if (!isBinopWithLit8OrLit16(currentInstruction)) {
continue;
}
Binop binop = currentInstruction.asBinop();
- if (!canBe2AddrInstruction(binop, lastUseOfBinopsWithLit8OrLit16NonConstantValues)) {
+ if (!canBe2AddrInstruction(
+ binop, currentInstructionNumber, lastUseOfBinopsWithLit8OrLit16NonConstantValues)) {
Value constValue = binopWithLit8OrLit16Constant(currentInstruction);
if (constValue.numberOfAllUsers() > 1) {
// No need to do the transformation if the const value is already used only one time.
@@ -1706,9 +1711,6 @@
}
}
- code.clearInstructionNumbers();
- assert code.hasNoInstructionNumbers();
-
assert code.isConsistentSSA();
}
@@ -1751,55 +1753,46 @@
}
/**
- * Estimate if a binary operation can be a 2addr form or not. It can be a 2addr form when an
+ * Estimate if a binary operation can be a binop/2addr form or not. It can be a 2addr form when an
* argument is no longer needed after the binary operation and can be overwritten. That is
* definitely the case if there is no path between the binary operation and all other usages.
*/
private static boolean canBe2AddrInstruction(
- Binop binop, Reference2IntMap<Value> lastUseOfRelevantValue) {
+ Binop binop, int binopInstructionNumber, Reference2IntMap<Value> lastUseOfRelevantValue) {
Value value = binopWithLit8OrLit16NonConstant(binop);
assert value != null;
- int number = lastUseOfRelevantValue.getInt(value);
- if (number > 0 && number > binop.getNumber()) {
+ int lastUseInstructionNumber = lastUseOfRelevantValue.getInt(value);
+ // The binop instruction is a user, so there is always a last use in the block.
+ assert lastUseInstructionNumber != -1;
+ if (lastUseInstructionNumber > binopInstructionNumber) {
return false;
}
- Iterable<Instruction> users =
+
+ Set<BasicBlock> noPathTo = Sets.newIdentityHashSet();
+ BasicBlock binopBlock = binop.getBlock();
+ Iterable<InstructionOrPhi> users =
value.debugUsers() != null
- ? Iterables.concat(value.uniqueUsers(), value.debugUsers())
- : value.uniqueUsers();
-
- for (Instruction user : users) {
- if (hasPath(binop, user)) {
+ ? Iterables.concat(value.uniqueUsers(), value.debugUsers(), value.uniquePhiUsers())
+ : Iterables.concat(value.uniqueUsers(), value.uniquePhiUsers());
+ for (InstructionOrPhi user : users) {
+ BasicBlock userBlock = user.getBlock();
+ if (userBlock == binopBlock) {
+ // All users in the current block are either before the binop instruction or the
+ // binop instruction itself.
+ continue;
+ }
+ if (noPathTo.contains(userBlock)) {
+ continue;
+ }
+ if (binopBlock.hasPathTo(userBlock)) {
return false;
}
- }
-
- for (Phi user : value.uniquePhiUsers()) {
- if (binop.getBlock().hasPathTo(user.getBlock())) {
- return false;
- }
+ noPathTo.add(userBlock);
}
return true;
}
- /**
- * Return true if there is a path between {@code source} instruction and {@code target}
- * instruction.
- */
- private static boolean hasPath(Instruction source, Instruction target) {
- BasicBlock sourceBlock = source.getBlock();
- BasicBlock targetBlock = target.getBlock();
- if (sourceBlock == targetBlock) {
- // Instructions must be numbered when getting here.
- assert source.getNumber() != -1;
- assert target.getNumber() != -1;
- return source.getNumber() < target.getNumber();
- }
-
- return source.getBlock().hasPathTo(targetBlock);
- }
-
public void shortenLiveRanges(IRCode code) {
// Currently, we are only shortening the live range of ConstNumbers in the entry block
// and ConstStrings with one user.
