Merge "Do not share constant use one time by a phi"
diff --git a/build.gradle b/build.gradle
index d13029e..4060a7a 100644
--- a/build.gradle
+++ b/build.gradle
@@ -317,6 +317,7 @@
task R8(type: com.github.jengelman.gradle.plugins.shadow.tasks.ShadowJar) {
from sourceSets.main.output
+ from files('LICENSE')
baseName 'r8'
classifier = null
version = null
@@ -342,6 +343,7 @@
task D8(type: com.github.jengelman.gradle.plugins.shadow.tasks.ShadowJar) {
from sourceSets.main.output
+ from files('LICENSE')
baseName 'd8'
classifier = null
version = null
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 21ed16e..7e2e851 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
@@ -42,6 +42,41 @@
this.valueNumberGenerator = valueNumberGenerator;
}
+ /**
+ * Trace blocks and attempt to put fallthrough blocks immediately after the block that
+ * falls through. When we fail to do that we create a new fallthrough block with an explicit
+ * goto to the actual fallthrough block.
+ */
+ public void traceBlocks() {
+ BasicBlock[] sorted = topologicallySortedBlocks();
+ clearMarks();
+ int nextBlockNumber = blocks.size();
+ LinkedList<BasicBlock> tracedBlocks = new LinkedList<>();
+ for (BasicBlock block : sorted) {
+ if (!block.isMarked()) {
+ block.mark();
+ tracedBlocks.add(block);
+ BasicBlock current = block;
+ BasicBlock fallthrough = block.exit().fallthroughBlock();
+ while (fallthrough != null && !fallthrough.isMarked()) {
+ fallthrough.mark();
+ tracedBlocks.add(fallthrough);
+ current = fallthrough;
+ fallthrough = fallthrough.exit().fallthroughBlock();
+ }
+ if (fallthrough != null) {
+ BasicBlock newFallthrough = BasicBlock.createGotoBlock(fallthrough, nextBlockNumber++);
+ current.exit().setFallthroughBlock(newFallthrough);
+ newFallthrough.getPredecessors().add(current);
+ fallthrough.replacePredecessor(current, newFallthrough);
+ newFallthrough.mark();
+ tracedBlocks.add(newFallthrough);
+ }
+ }
+ }
+ blocks = tracedBlocks;
+ }
+
private void ensureBlockNumbering() {
if (!numbered) {
numbered = true;
@@ -327,6 +362,10 @@
return normalExitBlock;
}
+ public void invalidateNormalExitBlock() {
+ normalExitBlock = null;
+ }
+
public ListIterator<BasicBlock> listIterator() {
return new BasicBlockIterator(this);
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/Return.java b/src/main/java/com/android/tools/r8/ir/code/Return.java
index 337ed71..ba2fcb0 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Return.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Return.java
@@ -67,7 +67,7 @@
@Override
public void buildDex(DexBuilder builder) {
- builder.add(this, createDexInstruction(builder));
+ builder.addReturn(this, createDexInstruction(builder));
}
@Override
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/DexBuilder.java b/src/main/java/com/android/tools/r8/ir/conversion/DexBuilder.java
index cbd8941..8540bf3 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/DexBuilder.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/DexBuilder.java
@@ -402,6 +402,33 @@
add(argument, new FallThroughInfo(argument));
}
+ public void addReturn(Return ret, Instruction dex) {
+ if (nextBlock != null) {
+ Return followingRet = nextBlock.exit().asReturn();
+ if (nextBlock.getInstructions().size() == 1
+ && followingRet != null
+ && ret.getReturnType() == followingRet.getReturnType()) {
+ if (ret.isReturnVoid() && followingRet.isReturnVoid()) {
+ addNop(ret);
+ return;
+ }
+ if (!ret.isReturnVoid()
+ && !followingRet.isReturnVoid()
+ && ret.returnValue().outType() == followingRet.returnValue().outType()) {
+ int thisRegister = registerAllocator.getRegisterForValue(
+ ret.returnValue(), ret.getNumber());
+ int otherRegister = registerAllocator.getRegisterForValue(
+ followingRet.returnValue(), followingRet.getNumber());
+ if (thisRegister == otherRegister) {
+ addNop(ret);
+ return;
+ }
+ }
+ }
+ }
+ add(ret, dex);
+ }
+
private void add(com.android.tools.r8.ir.code.Instruction ir, Info info) {
assert ir != null;
assert info != null;
@@ -436,10 +463,24 @@
return info;
}
}
- assert instruction != null && instruction.isGoto();
+ assert instruction != null;
+ if (instruction.isReturn()) {
+ assert getInfo(instruction) instanceof FallThroughInfo;
+ return getTargetInfo(computeNextBlock(block));
+ }
+ assert instruction.isGoto();
return getTargetInfo(instruction.asGoto().getTarget());
}
+ private BasicBlock computeNextBlock(BasicBlock block) {
+ ListIterator<BasicBlock> it = ir.listIterator();
+ BasicBlock current = it.next();
+ while (current != block) {
+ current = it.next();
+ }
+ return it.next();
+ }
+
// Helper for computing switch payloads.
private Nop createSwitchPayload(SwitchPayloadInfo info, int offset) {
Switch ir = info.ir;
@@ -844,8 +885,10 @@
// Set the size to the min of the size of the return and the size of the goto. When
// adding instructions, we use the return if the computed size matches the size of the
// return.
+ assert !(targetInfo instanceof FallThroughInfo);
size = Math.min(targetInfo.getSize(), size);
}
+ assert size != 0;
return size;
}
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 1b7a276..77f1a16 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
@@ -399,7 +399,7 @@
// Create block order and make sure that all blocks are immediately followed by their
// fallthrough block if any.
- traceBlocks(ir);
+ ir.traceBlocks();
// Clear the code so we don't build multiple times.
source.clear();
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 0ddd43a..8e5b26f 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
@@ -522,6 +522,9 @@
}
printMethod(code, "Optimized IR (SSA)");
+
+ codeRewriter.inlineReturnBlock(code);
+
// Perform register allocation.
RegisterAllocator registerAllocator = performRegisterAllocation(code, method);
method.setCode(code, registerAllocator, appInfo.dexItemFactory);
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 5570abe..5c1114b 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
@@ -87,6 +87,7 @@
import it.unimi.dsi.fastutil.objects.Object2IntLinkedOpenHashMap;
import it.unimi.dsi.fastutil.objects.Object2IntMap;
import java.util.ArrayList;
+import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
@@ -1475,6 +1476,87 @@
}
}
+ /**
+ * Inline the return block at its targets.
+ *
+ * The inlining of return mostly undoes the merge performed at IR build time. This helps avoid
+ * unneeded moves as values are forced into the same register at all returns, which there can be
+ * a lot of when compiling in debug mode. Measurements show that iterating the inlining of returns
+ * does not pay off as it can lead to code size increase, eg, when a sequence of ifs all jump to
+ * a common return.
+ */
+ public void inlineReturnBlock(IRCode code) {
+ BasicBlock block = code.getNormalExitBlock();
+ code.invalidateNormalExitBlock();
+ if (block == null
+ || block.getPredecessors().size() <= 1
+ || block.getInstructions().size() > 1) {
+ return;
+ }
+ int predIndex = 0;
+ for (BasicBlock pred : block.getPredecessors()) {
+ ListIterator<Instruction> iterator = pred.listIterator(pred.exit());
+ iterator.previous();
+ for (Instruction origInstruction : block.getInstructions()) {
+ assert origInstruction.isReturn();
+ // Create an instruction copy replacing phi values of this block by their operands.
+ Instruction instruction;
+ Return ret = origInstruction.asReturn();
+ if (ret.isReturnVoid()) {
+ instruction = new Return();
+ } else {
+ Value origValue = ret.returnValue();
+ Value copyValue = origValue.isPhi() && block.getPhis().contains(origValue)
+ ? origValue.asPhi().getOperand(predIndex)
+ : origValue;
+ instruction = new Return(copyValue, ret.getReturnType());
+ }
+ // Copy over each debug value replacing phi values of this block by their operands.
+ for (Value value : origInstruction.getDebugValues()) {
+ assert value.getLocalInfo() != null;
+ if (value.isPhi() && block.getPhis().contains(value)) {
+ Phi phi = value.asPhi();
+ Value operand = phi.getOperand(predIndex);
+ if (phi.getLocalInfo() == operand.getLocalInfo()) {
+ instruction.addDebugValue(operand);
+ } else {
+ // If the phi and its operand are different locals insert a local write.
+ Value localValue = code.createValue(phi.outType(), phi.getLocalInfo());
+ DebugLocalWrite write = new DebugLocalWrite(localValue, operand);
+ write.setBlock(pred);
+ iterator.add(write);
+ instruction.addDebugValue(localValue);
+ }
+ } else {
+ instruction.addDebugValue(value);
+ }
+ }
+ instruction.setBlock(pred);
+ iterator.add(instruction);
+ }
+ iterator.previous();
+ Instruction ret = iterator.next();
+ Instruction jump = iterator.next();
+ assert !iterator.hasNext();
+ jump.moveDebugValues(ret);
+ iterator.remove();
+ assert pred.exit().isReturn();
+ pred.removeSuccessor(block);
+ predIndex++;
+ }
+ // Clean out all users and remove the inlined block.
+ while (!block.getPredecessors().isEmpty()) {
+ block.removePredecessor(block.getPredecessors().get(0));
+ }
+ for (Instruction instruction : block.getInstructions()) {
+ for (Value value : instruction.inValues()) {
+ value.removeUser(instruction);
+ }
+ instruction.clearDebugValues();
+ }
+ code.removeBlocks(Collections.singletonList(block));
+ }
+
private static class ExpressionEquivalence extends Equivalence<Instruction> {
@Override
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java b/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java
index 2aa9015..1926f01 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java
@@ -369,10 +369,10 @@
}
}
spillCount = 0;
- if (localsChanged && shouldEmitChangesAtInstruction(instruction)) {
+ if (localsChanged && instruction.getBlock().exit() != instruction) {
DebugLocalsChange change = createLocalsChange(ending, starting);
if (change != null) {
- if (instruction.isDebugPosition() || instruction.isJumpInstruction()) {
+ if (instruction.isDebugPosition()) {
instructionIterator.previous();
instructionIterator.add(change);
instructionIterator.next();
@@ -505,14 +505,6 @@
return new DebugLocalsChange(ending, starting);
}
- private boolean shouldEmitChangesAtInstruction(Instruction instruction) {
- BasicBlock block = instruction.getBlock();
- // We emit local changes on all non-exit instructions or, since we have only a singe return
- // block, any exits directly targeting that.
- return instruction != block.exit()
- || (instruction.isGoto() && instruction.asGoto().getTarget() == code.getNormalExitBlock());
- }
-
private void clearState() {
liveAtEntrySets = null;
liveIntervals = null;
diff --git a/src/test/java/com/android/tools/r8/smali/IfSimplificationTest.java b/src/test/java/com/android/tools/r8/smali/IfSimplificationTest.java
index 919f569..9c41f21 100644
--- a/src/test/java/com/android/tools/r8/smali/IfSimplificationTest.java
+++ b/src/test/java/com/android/tools/r8/smali/IfSimplificationTest.java
@@ -443,6 +443,7 @@
DexCode code = method.getCode().asDexCode();
// TODO(sgjesse): Maybe this test is too fragile, as it leaves quite a lot of code, so the
// expectation might need changing with other optimizations.
- assertEquals(27, code.instructions.length);
+ // TODO(zerny): Consider optimizing the fallthrough branch of conditionals to not be return.
+ assertEquals(28, code.instructions.length);
}
}
