Instruction read set analysis
Change-Id: I7d6089119df4a6c7de02fdd5f8a7e589937e8069
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/fieldvalueanalysis/AbstractFieldSet.java b/src/main/java/com/android/tools/r8/ir/analysis/fieldvalueanalysis/AbstractFieldSet.java
new file mode 100644
index 0000000..60e799e
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/fieldvalueanalysis/AbstractFieldSet.java
@@ -0,0 +1,44 @@
+// Copyright (c) 2019, 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.analysis.fieldvalueanalysis;
+
+import com.android.tools.r8.graph.DexEncodedField;
+
+/**
+ * Implements a lifted subset lattice for fields.
+ *
+ * <p>An element can either be:
+ *
+ * <ol>
+ * <li>bottom, represented by {@link EmptyFieldSet},
+ * <li>a (possibly empty) set of fields, represented by {@link ConcreteMutableFieldSet}, or
+ * <li>top, represented by {@link UnknownFieldSet}.
+ * </ol>
+ *
+ * <p>Note that this class currently does not contain a {@code join()} method. Instead, the {@link
+ * ConcreteMutableFieldSet} has an {@link ConcreteMutableFieldSet#add(DexEncodedField)} and {@link
+ * ConcreteMutableFieldSet#addAll(ConcreteMutableFieldSet)} method. This is intentional, since the
+ * use of {@code join()} could lead to an excessive amount of set copying under the hood.
+ */
+public abstract class AbstractFieldSet {
+
+ public boolean isConcreteFieldSet() {
+ return false;
+ }
+
+ public ConcreteMutableFieldSet asConcreteFieldSet() {
+ return null;
+ }
+
+ public abstract boolean contains(DexEncodedField field);
+
+ public boolean isBottom() {
+ return false;
+ }
+
+ public boolean isTop() {
+ return false;
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/fieldvalueanalysis/ConcreteMutableFieldSet.java b/src/main/java/com/android/tools/r8/ir/analysis/fieldvalueanalysis/ConcreteMutableFieldSet.java
new file mode 100644
index 0000000..975272a
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/fieldvalueanalysis/ConcreteMutableFieldSet.java
@@ -0,0 +1,50 @@
+// Copyright (c) 2019, 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.analysis.fieldvalueanalysis;
+
+import com.android.tools.r8.graph.DexEncodedField;
+import com.android.tools.r8.utils.SetUtils;
+import com.google.common.collect.Sets;
+import java.util.Set;
+
+public class ConcreteMutableFieldSet extends AbstractFieldSet {
+
+ private final Set<DexEncodedField> fields;
+
+ public ConcreteMutableFieldSet() {
+ fields = Sets.newIdentityHashSet();
+ }
+
+ public ConcreteMutableFieldSet(DexEncodedField field) {
+ fields = SetUtils.newIdentityHashSet(field);
+ }
+
+ public void add(DexEncodedField field) {
+ fields.add(field);
+ }
+
+ public void addAll(ConcreteMutableFieldSet other) {
+ fields.addAll(other.fields);
+ }
+
+ public int size() {
+ return fields.size();
+ }
+
+ @Override
+ public boolean isConcreteFieldSet() {
+ return true;
+ }
+
+ @Override
+ public ConcreteMutableFieldSet asConcreteFieldSet() {
+ return this;
+ }
+
+ @Override
+ public boolean contains(DexEncodedField field) {
+ return fields.contains(field);
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/fieldvalueanalysis/EmptyFieldSet.java b/src/main/java/com/android/tools/r8/ir/analysis/fieldvalueanalysis/EmptyFieldSet.java
new file mode 100644
index 0000000..4897aeb
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/fieldvalueanalysis/EmptyFieldSet.java
@@ -0,0 +1,28 @@
+// Copyright (c) 2019, 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.analysis.fieldvalueanalysis;
+
+import com.android.tools.r8.graph.DexEncodedField;
+
+public class EmptyFieldSet extends AbstractFieldSet {
+
+ private static final EmptyFieldSet INSTANCE = new EmptyFieldSet();
+
+ private EmptyFieldSet() {}
+
+ public static EmptyFieldSet getInstance() {
+ return INSTANCE;
+ }
+
+ @Override
+ public boolean contains(DexEncodedField field) {
+ return false;
+ }
+
+ @Override
+ public boolean isBottom() {
+ return true;
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/fieldvalueanalysis/UnknownFieldSet.java b/src/main/java/com/android/tools/r8/ir/analysis/fieldvalueanalysis/UnknownFieldSet.java
new file mode 100644
index 0000000..9df87cc
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/fieldvalueanalysis/UnknownFieldSet.java
@@ -0,0 +1,28 @@
+// Copyright (c) 2019, 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.analysis.fieldvalueanalysis;
+
+import com.android.tools.r8.graph.DexEncodedField;
+
+public class UnknownFieldSet extends AbstractFieldSet {
+
+ private static final UnknownFieldSet INSTANCE = new UnknownFieldSet();
+
+ private UnknownFieldSet() {}
+
+ public static UnknownFieldSet getInstance() {
+ return INSTANCE;
+ }
+
+ @Override
+ public boolean contains(DexEncodedField field) {
+ return true;
+ }
+
+ @Override
+ public boolean isTop() {
+ return true;
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/modeling/LibraryMethodReadSetModeling.java b/src/main/java/com/android/tools/r8/ir/analysis/modeling/LibraryMethodReadSetModeling.java
new file mode 100644
index 0000000..57f8d2e
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/modeling/LibraryMethodReadSetModeling.java
@@ -0,0 +1,45 @@
+// Copyright (c) 2019, 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.analysis.modeling;
+
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.fieldvalueanalysis.AbstractFieldSet;
+import com.android.tools.r8.ir.analysis.fieldvalueanalysis.EmptyFieldSet;
+import com.android.tools.r8.ir.analysis.fieldvalueanalysis.UnknownFieldSet;
+import com.android.tools.r8.ir.code.InvokeMethod;
+import java.util.function.Predicate;
+
+/** Models if a given library method may cause a program field to be read. */
+public class LibraryMethodReadSetModeling {
+
+ public static AbstractFieldSet getModeledReadSetOrUnknown(
+ InvokeMethod invoke, DexItemFactory dexItemFactory) {
+ DexMethod invokedMethod = invoke.getInvokedMethod();
+
+ // Check if it is a library method that does not have side effects. In that case it is safe to
+ // assume that the method does not read any fields, since even if it did, it would not be able
+ // to do anything with the values it read (since we will remove such invocations without side
+ // effects).
+ Predicate<InvokeMethod> noSideEffectsPredicate =
+ dexItemFactory.libraryMethodsWithoutSideEffects.get(invokedMethod);
+ if (noSideEffectsPredicate != null && noSideEffectsPredicate.test(invoke)) {
+ return EmptyFieldSet.getInstance();
+ }
+
+ // Already handled above.
+ assert !dexItemFactory.classMethods.isReflectiveNameLookup(invokedMethod);
+
+ // Modeling of other library methods.
+ DexType holder = invokedMethod.holder;
+ if (holder == dexItemFactory.objectType) {
+ if (invokedMethod == dexItemFactory.objectMethods.constructor) {
+ return EmptyFieldSet.getInstance();
+ }
+ }
+ return UnknownFieldSet.getInstance();
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/code/FieldInstruction.java b/src/main/java/com/android/tools/r8/ir/code/FieldInstruction.java
index e041d5a..b95376e 100644
--- a/src/main/java/com/android/tools/r8/ir/code/FieldInstruction.java
+++ b/src/main/java/com/android/tools/r8/ir/code/FieldInstruction.java
@@ -11,6 +11,10 @@
import com.android.tools.r8.graph.DexField;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.ir.analysis.AbstractError;
+import com.android.tools.r8.ir.analysis.fieldvalueanalysis.AbstractFieldSet;
+import com.android.tools.r8.ir.analysis.fieldvalueanalysis.ConcreteMutableFieldSet;
+import com.android.tools.r8.ir.analysis.fieldvalueanalysis.EmptyFieldSet;
+import com.android.tools.r8.ir.analysis.fieldvalueanalysis.UnknownFieldSet;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import java.util.Collections;
import java.util.List;
@@ -131,4 +135,32 @@
// TODO(jsjeon): what if the target field is known to be non-null?
return true;
}
+
+ @Override
+ public AbstractFieldSet readSet(AppView<?> appView, DexType context) {
+ if (instructionMayTriggerMethodInvocation(appView, context)) {
+ // This may trigger class initialization, which could potentially read any field.
+ return UnknownFieldSet.getInstance();
+ }
+
+ if (isFieldGet()) {
+ DexField field = getField();
+ DexEncodedField encodedField = null;
+ if (appView.enableWholeProgramOptimizations()) {
+ encodedField = appView.appInfo().resolveField(field);
+ } else {
+ DexClass clazz = appView.definitionFor(field.holder);
+ if (clazz != null) {
+ encodedField = clazz.lookupField(field);
+ }
+ }
+ if (encodedField != null) {
+ return new ConcreteMutableFieldSet(encodedField);
+ }
+ return UnknownFieldSet.getInstance();
+ }
+
+ assert isFieldPut();
+ return EmptyFieldSet.getInstance();
+ }
}
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 03421cc..1a17a8b 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
@@ -17,6 +17,9 @@
import com.android.tools.r8.ir.analysis.constant.Bottom;
import com.android.tools.r8.ir.analysis.constant.ConstRangeLatticeElement;
import com.android.tools.r8.ir.analysis.constant.LatticeElement;
+import com.android.tools.r8.ir.analysis.fieldvalueanalysis.AbstractFieldSet;
+import com.android.tools.r8.ir.analysis.fieldvalueanalysis.EmptyFieldSet;
+import com.android.tools.r8.ir.analysis.fieldvalueanalysis.UnknownFieldSet;
import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
import com.android.tools.r8.ir.code.Assume.DynamicTypeAssumption;
import com.android.tools.r8.ir.code.Assume.NoAssumption;
@@ -540,6 +543,18 @@
}
/**
+ * Returns an abstraction of the set of fields that may possibly be read as a result of executing
+ * this instruction.
+ */
+ public AbstractFieldSet readSet(AppView<?> appView, DexType context) {
+ if (instructionMayTriggerMethodInvocation(appView, context)
+ && instructionMayHaveSideEffects(appView, context)) {
+ return UnknownFieldSet.getInstance();
+ }
+ return EmptyFieldSet.getInstance();
+ }
+
+ /**
* Returns true if this instruction need this value in a register.
*/
public boolean needsValueInRegister(Value value) {
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeDirect.java b/src/main/java/com/android/tools/r8/ir/code/InvokeDirect.java
index 9381fd1..48baef4 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeDirect.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeDirect.java
@@ -12,11 +12,15 @@
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexClass;
import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexEncodedMethod.TrivialInitializer;
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.ir.analysis.ClassInitializationAnalysis;
import com.android.tools.r8.ir.analysis.ClassInitializationAnalysis.AnalysisAssumption;
import com.android.tools.r8.ir.analysis.ClassInitializationAnalysis.Query;
+import com.android.tools.r8.ir.analysis.fieldvalueanalysis.AbstractFieldSet;
+import com.android.tools.r8.ir.analysis.fieldvalueanalysis.EmptyFieldSet;
+import com.android.tools.r8.ir.analysis.modeling.LibraryMethodReadSetModeling;
import com.android.tools.r8.ir.conversion.CfBuilder;
import com.android.tools.r8.ir.conversion.DexBuilder;
import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
@@ -277,4 +281,22 @@
return true;
}
+
+ @Override
+ public AbstractFieldSet readSet(AppView<?> appView, DexType context) {
+ DexMethod invokedMethod = getInvokedMethod();
+
+ // Trivial instance initializers do not read any fields.
+ if (appView.dexItemFactory().isConstructor(invokedMethod)) {
+ DexEncodedMethod singleTarget = lookupSingleTarget(appView, context);
+ if (singleTarget != null) {
+ TrivialInitializer info = singleTarget.getOptimizationInfo().getTrivialInitializerInfo();
+ if (info != null && info.isTrivialInstanceInitializer()) {
+ return EmptyFieldSet.getInstance();
+ }
+ }
+ }
+
+ return LibraryMethodReadSetModeling.getModeledReadSetOrUnknown(this, appView.dexItemFactory());
+ }
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java b/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
index c3db7ea..178da3f 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
@@ -11,6 +11,8 @@
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.ir.analysis.ClassInitializationAnalysis;
+import com.android.tools.r8.ir.analysis.fieldvalueanalysis.AbstractFieldSet;
+import com.android.tools.r8.ir.analysis.modeling.LibraryMethodReadSetModeling;
import com.android.tools.r8.ir.optimize.Inliner.InlineAction;
import com.android.tools.r8.ir.optimize.InliningOracle;
import com.android.tools.r8.ir.regalloc.RegisterAllocator;
@@ -119,4 +121,9 @@
public boolean instructionMayTriggerMethodInvocation(AppView<?> appView, DexType context) {
return true;
}
+
+ @Override
+ public AbstractFieldSet readSet(AppView<?> appView, DexType context) {
+ return LibraryMethodReadSetModeling.getModeledReadSetOrUnknown(this, appView.dexItemFactory());
+ }
}
