Eliminate redundant field loads.
Field loads that are dominated by a load of the same field on the same
object and for which there are no locking operations, stores to that
field, stores to static fields of other objects, or calls in between
the last load and this load can be eliminated.
This saves ~50kB on framework code.
Change-Id: I42853a6caf67e3e6caa47a0eac1227519b6a8490
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 8771b72..819c6f2 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
@@ -6,7 +6,6 @@
import static com.android.tools.r8.ir.code.IRCode.INSTRUCTION_NUMBER_DELTA;
import com.android.tools.r8.errors.CompilationError;
-import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.graph.DebugLocalInfo;
import com.android.tools.r8.graph.DebugLocalInfo.PrintLevel;
import com.android.tools.r8.graph.DexItemFactory;
@@ -468,7 +467,7 @@
return instruction;
}
}
- throw new Unreachable();
+ return null;
}
public void clearUserInfo() {
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 a52637f..52919c6 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
@@ -46,6 +46,7 @@
import com.android.tools.r8.ir.optimize.NonNullTracker;
import com.android.tools.r8.ir.optimize.Outliner;
import com.android.tools.r8.ir.optimize.PeepholeOptimizer;
+import com.android.tools.r8.ir.optimize.RedundantFieldLoadElimination;
import com.android.tools.r8.ir.optimize.classinliner.ClassInliner;
import com.android.tools.r8.ir.optimize.lambda.LambdaMerger;
import com.android.tools.r8.ir.regalloc.LinearScanRegisterAllocator;
@@ -686,6 +687,7 @@
codeRewriter.rewriteSwitch(code);
codeRewriter.processMethodsNeverReturningNormally(code);
codeRewriter.simplifyIf(code, typeEnvironment);
+ new RedundantFieldLoadElimination(code).run();
if (options.testing.invertConditionals) {
invertConditionalsForTesting(code);
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/RedundantFieldLoadElimination.java b/src/main/java/com/android/tools/r8/ir/optimize/RedundantFieldLoadElimination.java
new file mode 100644
index 0000000..24012b1
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/optimize/RedundantFieldLoadElimination.java
@@ -0,0 +1,193 @@
+// Copyright (c) 2018, 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.graph.DexField;
+import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.DominatorTree;
+import com.android.tools.r8.ir.code.FieldInstruction;
+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.Phi;
+import com.android.tools.r8.ir.code.Value;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+
+/**
+ * Eliminate redundant field loads.
+ *
+ * <p>Simple algorithm that goes through all blocks in one pass in dominator order and propagates
+ * active field sets across control-flow edges where the target has only one predecessor.
+ */
+// TODO(ager): Evaluate speed/size for computing active field sets in a fixed-point computation.
+public class RedundantFieldLoadElimination {
+
+ private final IRCode code;
+ private final DominatorTree dominatorTree;
+
+ // Maps keeping track of fields that have an already loaded value at basic block entry.
+ private final HashMap<BasicBlock, HashMap<FieldAndObject, Instruction>>
+ activeInstanceFieldsAtEntry = new HashMap<>();
+ private final HashMap<BasicBlock, HashMap<DexField, Instruction>> activeStaticFieldsAtEntry =
+ new HashMap<>();
+
+ // Maps keeping track of fields with already loaded values for the current block during
+ // elimination.
+ private HashMap<FieldAndObject, Instruction> activeInstanceFields;
+ private HashMap<DexField, Instruction> activeStaticFields;
+
+ public RedundantFieldLoadElimination(IRCode code) {
+ this.code = code;
+ dominatorTree = new DominatorTree(code);
+ }
+
+ private static class FieldAndObject {
+ private final DexField field;
+ private final Value object;
+
+ private FieldAndObject(DexField field, Value receiver) {
+ this.field = field;
+ this.object = receiver;
+ }
+
+ @Override
+ public int hashCode() {
+ return field.hashCode() * 7 + object.hashCode();
+ }
+
+ @Override
+ public boolean equals(Object other) {
+ if (!(other instanceof FieldAndObject)) {
+ return false;
+ }
+ FieldAndObject o = (FieldAndObject) other;
+ return o.object == object && o.field == field;
+ }
+ }
+
+ public void run() {
+ for (BasicBlock block : dominatorTree.getSortedBlocks()) {
+ activeInstanceFields =
+ activeInstanceFieldsAtEntry.containsKey(block)
+ ? activeInstanceFieldsAtEntry.get(block)
+ : new HashMap<>();
+ activeStaticFields =
+ activeStaticFieldsAtEntry.containsKey(block)
+ ? activeStaticFieldsAtEntry.get(block)
+ : new HashMap<>();
+ InstructionListIterator it = block.listIterator();
+ while (it.hasNext()) {
+ Instruction instruction = it.next();
+ if (instruction.isFieldInstruction()) {
+ DexField field = instruction.asFieldInstruction().getField();
+ if (instruction.isInstancePut() || instruction.isStaticPut()) {
+ killActiveFields(instruction.asFieldInstruction());
+ } else if (instruction.isInstanceGet() && !instruction.outValue().hasLocalInfo()) {
+ Value object = instruction.asInstanceGet().object();
+ FieldAndObject fieldAndObject = new FieldAndObject(field, object);
+ if (activeInstanceFields.containsKey(fieldAndObject)) {
+ Instruction active = activeInstanceFields.get(fieldAndObject);
+ eliminateRedundantRead(it, instruction, active);
+ } else {
+ activeInstanceFields.put(fieldAndObject, instruction);
+ }
+ } else if (instruction.isStaticGet() && !instruction.outValue().hasLocalInfo()) {
+ if (activeStaticFields.containsKey(field)) {
+ Instruction active = activeStaticFields.get(field);
+ eliminateRedundantRead(it, instruction, active);
+ } else {
+ // A field get on a different class can cause <clinit> to run and change static
+ // field values.
+ killActiveFields(instruction.asFieldInstruction());
+ activeStaticFields.put(field, instruction);
+ }
+ }
+ }
+ if (instruction.isMonitor() || instruction.isInvokeMethod()) {
+ activeInstanceFields.clear();
+ activeStaticFields.clear();
+ }
+ }
+ propagateActiveFieldsFrom(block);
+ }
+ assert code.isConsistentSSA();
+ }
+
+ private void propagateActiveFieldsFrom(BasicBlock block) {
+ for (BasicBlock successor : block.getSuccessors()) {
+ // Allow propagation across exceptional edges, just be careful not to propagate if the
+ // throwing instruction is a field instruction.
+ if (successor.getPredecessors().size() == 1) {
+ if (block.hasCatchSuccessor(successor)) {
+ Instruction exceptionalExit = block.exceptionalExit();
+ if (exceptionalExit != null && exceptionalExit.isFieldInstruction()) {
+ killActiveFieldsForExceptionalExit(exceptionalExit.asFieldInstruction());
+ }
+ }
+ assert !activeInstanceFieldsAtEntry.containsKey(successor);
+ activeInstanceFieldsAtEntry.put(successor, new HashMap<>(activeInstanceFields));
+ assert !activeStaticFieldsAtEntry.containsKey(successor);
+ activeStaticFieldsAtEntry.put(successor, new HashMap<>(activeStaticFields));
+ }
+ }
+ }
+
+ private void killActiveFields(FieldInstruction instruction) {
+ DexField field = instruction.getField();
+ if (instruction.isInstancePut()) {
+ // Remove all the field/object pairs that refer to this field to make sure
+ // that we are conservative.
+ List<FieldAndObject> keysToRemove = new ArrayList<>();
+ for (FieldAndObject key : activeInstanceFields.keySet()) {
+ if (key.field == field) {
+ keysToRemove.add(key);
+ }
+ }
+ keysToRemove.forEach((k) -> activeInstanceFields.remove(k));
+ } else if (instruction.isInstanceGet()) {
+ Value object = instruction.asInstanceGet().object();
+ FieldAndObject fieldAndObject = new FieldAndObject(field, object);
+ activeInstanceFields.remove(fieldAndObject);
+ } else if (instruction.isStaticPut()) {
+ if (field.clazz != code.method.method.holder) {
+ // Accessing a static field on a different object could cause <clinit> to run which
+ // could modify any static field on any other object.
+ activeStaticFields.clear();
+ } else {
+ activeStaticFields.remove(field);
+ }
+ } else if (instruction.isStaticGet()) {
+ if (field.clazz != code.method.method.holder) {
+ // Accessing a static field on a different object could cause <clinit> to run which
+ // could modify any static field on any other object.
+ activeStaticFields.clear();
+ }
+ }
+ }
+
+ // If a field get instruction throws an exception it did not have an effect on the
+ // value of the field. Therefore, when propagating across exceptional edges for a
+ // field get instruction we have to exclude that field from the set of known
+ // field values.
+ private void killActiveFieldsForExceptionalExit(FieldInstruction instruction) {
+ DexField field = instruction.getField();
+ if (instruction.isInstanceGet()) {
+ Value object = instruction.asInstanceGet().object();
+ FieldAndObject fieldAndObject = new FieldAndObject(field, object);
+ activeInstanceFields.remove(fieldAndObject);
+ } else if (instruction.isStaticGet()) {
+ activeStaticFields.remove(field);
+ }
+ }
+
+ private void eliminateRedundantRead(
+ InstructionListIterator it, Instruction redundant, Instruction active) {
+ redundant.outValue().replaceUsers(active.outValue());
+ it.removeOrReplaceByDebugLocalRead();
+ active.outValue().uniquePhiUsers().forEach(Phi::removeTrivialPhi);
+ }
+}
diff --git a/src/test/examples/uninitializedfinal/UninitializedFinalFieldLeak.java b/src/test/examples/uninitializedfinal/UninitializedFinalFieldLeak.java
new file mode 100644
index 0000000..781d2b4
--- /dev/null
+++ b/src/test/examples/uninitializedfinal/UninitializedFinalFieldLeak.java
@@ -0,0 +1,57 @@
+// Copyright (c) 2018 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 uninitializedfinal;
+
+// Test that leaks an instance before its final field has been initialized to a thread that
+// reads that field. This tests that redundant field load elimination does not eliminate
+// field reads (even of final fields) that cross a monitor operation.
+public class UninitializedFinalFieldLeak {
+
+ public static class PollingThread extends Thread {
+ public int result = 0;
+ UninitializedFinalFieldLeak f;
+
+ PollingThread(UninitializedFinalFieldLeak f) {
+ this.f = f;
+ }
+
+ // Read the field a number of times. Then lock on the object to await field initialization.
+ public void run() {
+ result += f.i;
+ result += f.i;
+ result += f.i;
+ f.threadReadsDone = true;
+ synchronized (f) {
+ result += f.i;
+ }
+ // The right result is 42. Reading the uninitialized 0 three times and then
+ // reading the initialized value. It is safe to remove the two redundant loads
+ // before the monitor operation.
+ System.out.println(result);
+ }
+ }
+
+ public final int i;
+ public volatile boolean threadReadsDone = false;
+
+ public UninitializedFinalFieldLeak() throws InterruptedException {
+ // Leak the object to a thread and start the thread with the lock on the object taken.
+ // Then allow the other thread to run and read the uninitialized field.
+ // Finally, initialize the field and release the lock.
+ PollingThread t = new PollingThread(this);
+ synchronized (this) {
+ t.start();
+ while (!threadReadsDone) {
+ Thread.yield();
+ }
+ i = 42;
+ }
+ t.join();
+ }
+
+ public static void main(String[] args) throws InterruptedException {
+ new UninitializedFinalFieldLeak();
+ }
+}
diff --git a/src/test/java/com/android/tools/r8/R8RunExamplesTest.java b/src/test/java/com/android/tools/r8/R8RunExamplesTest.java
index 087012c..36d924f 100644
--- a/src/test/java/com/android/tools/r8/R8RunExamplesTest.java
+++ b/src/test/java/com/android/tools/r8/R8RunExamplesTest.java
@@ -45,9 +45,11 @@
"instancevariable.InstanceVariable",
"instanceofstring.InstanceofString",
"invoke.Invoke",
+ "invokeempty.InvokeEmpty",
"jumbostring.JumboString",
"loadconst.LoadConst",
"loop.UdpServer",
+ "nestedtrycatches.NestedTryCatches",
"newarray.NewArray",
"regalloc.RegAlloc",
"returns.Returns",
@@ -58,9 +60,7 @@
"throwing.Throwing",
"trivial.Trivial",
"trycatch.TryCatch",
- "nestedtrycatches.NestedTryCatches",
"trycatchmany.TryCatchMany",
- "invokeempty.InvokeEmpty",
"regress.Regress",
"regress2.Regress2",
"regress_37726195.Regress",
@@ -81,6 +81,7 @@
"enclosingmethod_proguarded.Main",
"interfaceinlining.Main",
"switchmaps.Switches",
+ "uninitializedfinal.UninitializedFinalFieldLeak",
};
List<String[]> fullTestList = new ArrayList<>(tests.length * 2);
