Merge "Eliminate redundant field loads."
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);
