Refactor user replacement to avoid concurrent modification errors.
R=ager
Change-Id: I9fdc4a457a82b9b0a2f84125638e04801e306313
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 13325d8..e99dbf1 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
@@ -14,9 +14,11 @@
import com.android.tools.r8.utils.InternalOptions;
import com.android.tools.r8.utils.StringUtils;
import com.android.tools.r8.utils.StringUtils.BraceType;
-import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
import java.util.ArrayList;
+import java.util.HashSet;
import java.util.List;
+import java.util.Set;
public abstract class Instruction {
@@ -24,7 +26,7 @@
protected final List<Value> inValues = new ArrayList<>();
private BasicBlock block = null;
private int number = -1;
- private List<Value> debugValues = null;
+ private Set<Value> debugValues = null;
protected Instruction(Value outValue) {
setOutValue(outValue);
@@ -70,7 +72,7 @@
public void addDebugValue(Value value) {
assert value.getLocalInfo() != null;
if (debugValues == null) {
- debugValues = new ArrayList<>();
+ debugValues = new HashSet<>();
}
debugValues.add(value);
value.addDebugUser(this);
@@ -92,39 +94,25 @@
public abstract void buildDex(DexBuilder builder);
- public void replaceValue(Value oldValue, Value newValue) {
+ public void replaceValue(Value oldValue, Value newValue, List<Instruction> toRemove) {
for (int i = 0; i < inValues.size(); i++) {
if (oldValue == inValues.get(i)) {
inValues.set(i, newValue);
newValue.addUser(this);
- oldValue.removeUser(this);
+ toRemove.add(this);
}
}
}
- // Similar to Phi::replaceTrivialPhi, removal can cause a concurrent modification error.
- // TODO(ager): Consider unifying with other replace methods and avoid the C.M.E.
- public boolean replaceDebugValue(Value oldValue, Value newValue) {
- if (debugValues == null) {
- return false;
- }
- int found = -1;
- for (int i = 0; i < debugValues.size(); i++) {
- if (oldValue == debugValues.get(i)) {
- assert found == -1;
- found = i;
- if (newValue.getLocalInfo() != null) {
- // TODO(zerny): Insert a write if replacing a phi with different debug-local info.
- debugValues.set(i, newValue);
- newValue.addDebugUser(this);
- }
+ public void replaceDebugValue(Value oldValue, Value newValue, List<Instruction> toRemove) {
+ if (debugValues.remove(oldValue)) {
+ toRemove.add(this);
+ if (newValue.getLocalInfo() != null) {
+ // TODO(zerny): Insert a write if replacing a phi with different debug-local info.
+ addDebugValue(newValue);
}
+ // TODO(zerny): Else: Insert a write if replacing a phi with associated debug-local info.
}
- if (found >= 0 && newValue.getLocalInfo() == null) {
- // TODO(zerny): Insert a write if replacing a phi with associated debug-local info.
- debugValues.remove(found);
- }
- return found >= 0;
}
/**
@@ -324,8 +312,8 @@
return outValue == null ? null : outValue.getLocalInfo();
}
- public List<Value> getDebugValues() {
- return debugValues != null ? debugValues : ImmutableList.of();
+ public Set<Value> getDebugValues() {
+ return debugValues != null ? debugValues : ImmutableSet.of();
}
public boolean isArrayGet() {
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 185d2fd..96069bf 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
@@ -10,18 +10,19 @@
import com.android.tools.r8.utils.CfgPrinter;
import com.android.tools.r8.utils.ListUtils;
import com.android.tools.r8.utils.StringUtils;
-import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
+import java.util.Map.Entry;
import java.util.Set;
public class Phi extends Value {
private final BasicBlock block;
private final List<Value> operands = new ArrayList<>();
- private List<Value> debugValues = null;
+ private Set<Value> debugValues = null;
// Trivial phis are eliminated during IR construction. When a trivial phi is eliminated
// we need to update all references to it. A phi can be referenced from phis, instructions
@@ -101,7 +102,7 @@
public void addDebugValue(Value value) {
assert value.getLocalInfo() != null;
if (debugValues == null) {
- debugValues = new ArrayList<>();
+ debugValues = new HashSet<>();
}
debugValues.add(value);
value.addDebugPhiUser(this);
@@ -154,31 +155,22 @@
current.removePhiUser(this);
}
- // Removing the phi user from the current value leads to concurrent modification errors
- // during trivial phi elimination. It is safe to not remove the phi user from current
- // since current will be unreachable after trivial phi elimination.
- // TODO(ager): can we unify the these replace methods and avoid the concurrent modification
- // issue?
- private void replaceTrivialPhi(Value current, Value newValue) {
+ void replaceTrivialPhi(Value current, Value newValue, List<Phi> toRemove) {
for (int i = 0; i < operands.size(); i++) {
if (operands.get(i) == current) {
operands.set(i, newValue);
newValue.addPhiUser(this);
+ toRemove.add(this);
}
}
}
- private void replaceTrivialDebugPhi(Value current, Value newValue) {
- if (debugValues == null) {
- return;
- }
+ void replaceTrivialDebugPhi(Value current, Value newValue, List<Phi> toRemove) {
assert current.getLocalInfo() != null;
assert current.getLocalInfo() == newValue.getLocalInfo();
- for (int i = 0; i < debugValues.size(); i++) {
- if (debugValues.get(i) == current) {
- debugValues.set(i, newValue);
- newValue.addDebugPhiUser(this);
- }
+ if (debugValues.remove(current)) {
+ addDebugValue(newValue);
+ toRemove.add(this);
}
}
@@ -213,35 +205,17 @@
same = op;
}
assert isTrivialPhi();
+ assert same != null : "ill-defined phi";
// Removing this phi, so get rid of it as a phi user from all of the operands to avoid
// recursively getting back here with the same phi. If the phi has itself as an operand
// that also removes the self-reference.
for (Value op : operands) {
op.removePhiUser(this);
}
- // Replace this phi with the unique value in all users.
- for (Instruction user : uniqueUsers()) {
- user.replaceValue(this, same);
- }
- for (Phi user : uniquePhiUsers()) {
- user.replaceTrivialPhi(this, same);
- }
- if (debugUsers() != null) {
- List<Instruction> removed = new ArrayList<>();
- for (Instruction user : debugUsers()) {
- if (user.replaceDebugValue(this, same)) {
- removed.add(user);
- }
- }
- removed.forEach(this::removeDebugUser);
- for (Phi user : debugPhiUsers()) {
- user.replaceTrivialDebugPhi(this, same);
- }
- }
// If IR construction is taking place, update the definition users.
if (definitionUsers != null) {
for (Map<Integer, Value> user : definitionUsers) {
- for (Map.Entry<Integer, Value> entry : user.entrySet()) {
+ for (Entry<Integer, Value> entry : user.entrySet()) {
if (entry.getValue() == this) {
entry.setValue(same);
if (same.isPhi()) {
@@ -251,9 +225,14 @@
}
}
}
- // Try to simplify phi users that might now have become trivial.
- for (Phi user : uniquePhiUsers()) {
- user.removeTrivialPhi();
+ {
+ Set<Phi> phiUsersToSimplify = uniquePhiUsers();
+ // Replace this phi with the unique value in all users.
+ replaceInUsers(same);
+ // Try to simplify phi users that might now have become trivial.
+ for (Phi user : phiUsersToSimplify) {
+ user.removeTrivialPhi();
+ }
}
// Get rid of the phi itself.
block.removePhi(this);
@@ -349,7 +328,7 @@
return true;
}
- public List<Value> getDebugValues() {
- return debugValues != null ? debugValues : ImmutableList.of();
+ public Set<Value> getDebugValues() {
+ return debugValues != null ? debugValues : ImmutableSet.of();
}
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/Value.java b/src/main/java/com/android/tools/r8/ir/code/Value.java
index 78cb4a5..07f6913 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Value.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Value.java
@@ -308,27 +308,52 @@
}
if (debugData != null) {
for (Instruction user : debugUsers()) {
- user.getDebugValues().replaceAll(v -> {
- if (v == this) {
- newValue.addDebugUser(user);
- return newValue;
- }
- return v;
- });
+ if (user.getDebugValues().remove(this)) {
+ user.addDebugValue(newValue);
+ }
}
for (Phi user : debugPhiUsers()) {
- user.getDebugValues().replaceAll(v -> {
- if (v == this) {
- newValue.addDebugPhiUser(user);
- return newValue;
- }
- return v;
- });
+ if (user.getDebugValues().remove(this)) {
+ user.addDebugValue(newValue);
+ }
}
}
clearUsers();
}
+ public void replaceInUsers(Value newValue) {
+ if (!uniqueUsers().isEmpty()) {
+ List<Instruction> toRemove = new ArrayList<>(uniqueUsers().size());
+ for (Instruction user : uniqueUsers()) {
+ user.replaceValue(this, newValue, toRemove);
+ }
+ toRemove.forEach(this::removeUser);
+ }
+ if (!uniquePhiUsers().isEmpty()) {
+ List<Phi> toRemove = new ArrayList<>(uniquePhiUsers().size());
+ for (Phi user : uniquePhiUsers()) {
+ user.replaceTrivialPhi(this, newValue, toRemove);
+ }
+ toRemove.forEach(this::removePhiUser);
+ }
+ if (debugData != null) {
+ if (!debugUsers().isEmpty()) {
+ List<Instruction> toRemove = new ArrayList<>(debugUsers().size());
+ for (Instruction user : debugUsers()) {
+ user.replaceDebugValue(this, newValue, toRemove);
+ }
+ toRemove.forEach(this::removeDebugUser);
+ }
+ if (!debugPhiUsers().isEmpty()) {
+ List<Phi> toRemove = new ArrayList<>(debugPhiUsers().size());
+ for (Phi user : debugPhiUsers()) {
+ user.replaceTrivialDebugPhi(this, newValue, toRemove);
+ }
+ toRemove.forEach(this::removeDebugPhiUser);
+ }
+ }
+ }
+
public void setLiveIntervals(LiveIntervals intervals) {
assert liveIntervals == null;
liveIntervals = intervals;
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 3a89759..e78595d 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
@@ -1103,13 +1103,15 @@
assert instruction.outValue().numberOfUsers() != 0;
ConstNumber constNumber = instruction.asConstNumber();
Value constantValue = instruction.outValue();
+ List<Instruction> toRemove = new ArrayList<>(constantValue.uniqueUsers().size());
for (Instruction user : constantValue.uniqueUsers()) {
ConstNumber newCstNum = ConstNumber.copyOf(code, constNumber);
InstructionListIterator iterator = user.getBlock().listIterator(user);
iterator.previous();
iterator.add(newCstNum);
- user.replaceValue(constantValue, newCstNum.outValue());
+ user.replaceValue(constantValue, newCstNum.outValue(), toRemove);
}
+ toRemove.forEach(constantValue::removeUser);
}
}
} else {
