Fix nondeterministic insertion of spill/restore moves
Bug: 197643889
Change-Id: Id6fea8e9025a3e698cc16a02ebbafabb7382289d
diff --git a/src/main/java/com/android/tools/r8/ir/code/IRCode.java b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
index 0447c1a..e5c792f 100644
--- a/src/main/java/com/android/tools/r8/ir/code/IRCode.java
+++ b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
@@ -27,6 +27,7 @@
import com.android.tools.r8.utils.DequeUtils;
import com.android.tools.r8.utils.InternalOptions;
import com.android.tools.r8.utils.IteratorUtils;
+import com.android.tools.r8.utils.LinkedHashSetUtils;
import com.android.tools.r8.utils.ListUtils;
import com.android.tools.r8.utils.SetUtils;
import com.android.tools.r8.utils.StringUtils;
@@ -61,7 +62,7 @@
public static class LiveAtEntrySets {
// Set of live SSA values (regardless of whether they denote a local variable).
- public final Set<Value> liveValues;
+ public final LinkedHashSet<Value> liveValues;
// Subset of live local-variable values.
public final Set<Value> liveLocalValues;
@@ -69,7 +70,7 @@
public final Deque<Value> liveStackValues;
public LiveAtEntrySets(
- Set<Value> liveValues, Set<Value> liveLocalValues, Deque<Value> liveStackValues) {
+ LinkedHashSet<Value> liveValues, Set<Value> liveLocalValues, Deque<Value> liveStackValues) {
assert liveValues.containsAll(liveLocalValues);
this.liveValues = liveValues;
this.liveLocalValues = liveLocalValues;
@@ -176,14 +177,14 @@
while (!worklist.isEmpty()) {
BasicBlock block = worklist.poll();
// Note that the iteration order of live values matters when inserting spill/restore moves.
- Set<Value> live = new LinkedHashSet<>();
+ LinkedHashSet<Value> live = new LinkedHashSet<>();
Set<Value> liveLocals = Sets.newIdentityHashSet();
Deque<Value> liveStack = new ArrayDeque<>();
Set<BasicBlock> exceptionalSuccessors = block.getCatchHandlers().getUniqueTargets();
for (BasicBlock succ : block.getSuccessors()) {
LiveAtEntrySets liveAtSucc = liveAtEntrySets.get(succ);
if (liveAtSucc != null) {
- live.addAll(liveAtSucc.liveValues);
+ LinkedHashSetUtils.addAll(live, liveAtSucc.liveValues);
liveLocals.addAll(liveAtSucc.liveLocalValues);
// The stack is only allowed to be non-empty in the case of linear-flow (so-far).
// If succ is an exceptional successor the successor stack should be empty
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java b/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java
index e98adec..537d9af 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java
@@ -38,6 +38,7 @@
import com.android.tools.r8.ir.regalloc.RegisterPositions.Type;
import com.android.tools.r8.logging.Log;
import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.LinkedHashSetUtils;
import com.android.tools.r8.utils.SetUtils;
import com.android.tools.r8.utils.StringUtils;
import com.google.common.collect.HashMultiset;
@@ -60,6 +61,7 @@
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
+import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
@@ -2524,9 +2526,10 @@
Map<BasicBlock, LiveAtEntrySets> liveAtEntrySets,
List<LiveIntervals> liveIntervals) {
for (BasicBlock block : code.topologicallySortedBlocks()) {
- Set<Value> live = Sets.newIdentityHashSet();
- Set<Value> phiOperands = Sets.newIdentityHashSet();
- Set<Value> liveAtThrowingInstruction = Sets.newIdentityHashSet();
+ // Linked collections to ensure determinism of liveIntervals (see also b/197643889).
+ LinkedHashSet<Value> live = Sets.newLinkedHashSet();
+ LinkedHashSet<Value> phiOperands = Sets.newLinkedHashSet();
+ LinkedHashSet<Value> liveAtThrowingInstruction = Sets.newLinkedHashSet();
Set<BasicBlock> exceptionalSuccessors = block.getCatchHandlers().getUniqueTargets();
for (BasicBlock successor : block.getSuccessors()) {
// Values live at entry to a block that is an exceptional successor are only live
@@ -2534,9 +2537,10 @@
// the block only if they are used in normal flow as well.
boolean isExceptionalSuccessor = exceptionalSuccessors.contains(successor);
if (isExceptionalSuccessor) {
- liveAtThrowingInstruction.addAll(liveAtEntrySets.get(successor).liveValues);
+ LinkedHashSetUtils.addAll(
+ liveAtThrowingInstruction, liveAtEntrySets.get(successor).liveValues);
} else {
- live.addAll(liveAtEntrySets.get(successor).liveValues);
+ LinkedHashSetUtils.addAll(live, liveAtEntrySets.get(successor).liveValues);
}
// Exception blocks should not have any phis (if an exception block has more than one
// predecessor, then we insert a split block in-between).
@@ -2546,7 +2550,7 @@
phiOperands.add(phi.getOperand(successor.getPredecessors().indexOf(block)));
}
}
- live.addAll(phiOperands);
+ LinkedHashSetUtils.addAll(live, phiOperands);
List<Instruction> instructions = block.getInstructions();
for (Value value : live) {
int end = block.entry().getNumber() + instructions.size() * INSTRUCTION_NUMBER_DELTA;
@@ -2635,7 +2639,9 @@
// In debug mode, or if the method is reachability sensitive, extend the live range
// to cover the full scope of a local variable (encoded as debug values).
int number = instruction.getNumber();
- for (Value use : instruction.getDebugValues()) {
+ List<Value> sortedDebugValues = new ArrayList<>(instruction.getDebugValues());
+ sortedDebugValues.sort(Value::compareTo);
+ for (Value use : sortedDebugValues) {
assert use.needsRegister();
if (!live.contains(use)) {
live.add(use);
diff --git a/src/main/java/com/android/tools/r8/utils/LinkedHashSetUtils.java b/src/main/java/com/android/tools/r8/utils/LinkedHashSetUtils.java
new file mode 100644
index 0000000..d7812fb
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/LinkedHashSetUtils.java
@@ -0,0 +1,14 @@
+// Copyright (c) 2021, 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.utils;
+
+import java.util.LinkedHashSet;
+
+public class LinkedHashSetUtils {
+
+ public static <T> void addAll(LinkedHashSet<T> set, LinkedHashSet<T> elements) {
+ set.addAll(elements);
+ }
+}
