Deduplicate phi just after Ir building
- Sccp can generate duplicate Phi, deduplicate them only on block
where it could be needed.
Change-Id: I5ec08d2c8696eea18b0a9d156ee685eee792501f
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/constant/SparseConditionalConstantPropagation.java b/src/main/java/com/android/tools/r8/ir/analysis/constant/SparseConditionalConstantPropagation.java
index be3fc05..d5bf54b 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/constant/SparseConditionalConstantPropagation.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/constant/SparseConditionalConstantPropagation.java
@@ -13,12 +13,12 @@
import com.android.tools.r8.ir.code.Phi;
import com.android.tools.r8.ir.code.Switch;
import com.android.tools.r8.ir.code.Value;
-import com.google.common.base.Equivalence;
-import com.google.common.base.Equivalence.Wrapper;
+import java.util.ArrayList;
import java.util.BitSet;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
+import java.util.List;
import java.util.Map;
/**
@@ -75,30 +75,9 @@
assert code.isConsistentSSA();
}
- private static class PhiEquivalence extends Equivalence<Phi> {
-
- @Override
- protected boolean doEquivalent(Phi a, Phi b) {
- assert a.getBlock() == b.getBlock();
- for (int i = 0; i < a.getOperands().size(); i++) {
- if (a.getOperand(i) != b.getOperand(i)) {
- return false;
- }
- }
- return true;
- }
-
- @Override
- protected int doHash(Phi phi) {
- int hash = 0;
- for (Value value : phi.getOperands()) {
- hash = hash * 13 + value.hashCode();
- }
- return hash;
- }
- }
-
private void rewriteCode() {
+ List<BasicBlock> blockToAnalyze = new ArrayList<>();
+
mapping.entrySet().stream()
.filter((entry) -> entry.getValue().isConst())
.forEach((entry) -> {
@@ -109,6 +88,7 @@
// D8 relies on dead code removal to get rid of the dead phi itself.
if (value.numberOfAllUsers() != 0) {
BasicBlock block = value.asPhi().getBlock();
+ blockToAnalyze.add(block);
// Create a new constant, because it can be an existing constant that flow directly
// into the phi.
ConstNumber newConst = ConstNumber.copyOf(code, evaluatedConst);
@@ -130,18 +110,8 @@
}
});
- for (BasicBlock block : code.blocks) {
- PhiEquivalence equivalence = new PhiEquivalence();
- HashMap<Wrapper<Phi>, Phi> phis = new HashMap<>();
- for (Phi phi : block.getPhis()) {
- Wrapper<Phi> key = equivalence.wrap(phi);
- Phi replacement = phis.get(key);
- if (replacement != null) {
- phi.replaceUsers(replacement);
- } else {
- phis.put(key, phi);
- }
- }
+ for (BasicBlock block : blockToAnalyze) {
+ block.deduplicatePhis();
}
code.removeAllTrivialPhis();
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 3e685a2..fc74be1 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
@@ -14,6 +14,8 @@
import com.android.tools.r8.utils.ListUtils;
import com.android.tools.r8.utils.StringUtils;
import com.android.tools.r8.utils.StringUtils.BraceType;
+import com.google.common.base.Equivalence;
+import com.google.common.base.Equivalence.Wrapper;
import com.google.common.collect.ImmutableList;
import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
import java.util.ArrayDeque;
@@ -21,6 +23,7 @@
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
+import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
@@ -1398,4 +1401,46 @@
return false;
}
+
+ private static class PhiEquivalence extends Equivalence<Phi> {
+ @Override
+ protected boolean doEquivalent(Phi a, Phi b) {
+ assert a.getBlock() == b.getBlock();
+ for (int i = 0; i < a.getOperands().size(); i++) {
+ if (a.getOperand(i) != b.getOperand(i)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ @Override
+ protected int doHash(Phi phi) {
+ int hash = 0;
+ for (Value value : phi.getOperands()) {
+ hash = hash * 13 + value.hashCode();
+ }
+ return hash;
+ }
+ }
+
+ public void deduplicatePhis() {
+ PhiEquivalence equivalence = new PhiEquivalence();
+ HashMap<Wrapper<Phi>, Phi> wrapper2phi = new HashMap<>();
+ Iterator<Phi> phiIt = phis.iterator();
+ while (phiIt.hasNext()) {
+ Phi phi = phiIt.next();
+ Wrapper<Phi> key = equivalence.wrap(phi);
+ Phi replacement = wrapper2phi.get(key);
+ if (replacement != null) {
+ phi.replaceUsers(replacement);
+ for (Value operand : phi.getOperands()) {
+ operand.removePhiUser(phi);
+ }
+ phiIt.remove();
+ } else {
+ wrapper2phi.put(key, phi);
+ }
+ }
+ }
}
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 e4168ea..b392308 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
@@ -414,6 +414,12 @@
clearCanonicalizationMaps();
source = null;
+ for (BasicBlock block : blocks) {
+ block.deduplicatePhis();
+ }
+
+ ir.removeAllTrivialPhis();
+
assert ir.isConsistentSSA();
return ir;
}
