Make output deterministic for dex code with invoke-custom.

DexCallSites and DexMethodHandles were not sorted. Sorting is not
needed for correct code, but it is needed for deterministic output.

The complication for DexCallSites is that two call sites can be
equal and only differ in identity. Therefore, we have to have
some external thing to sort based on. This change uses the
method and instruction offset of the invoke-custom in the output
that the call site is needed for to deterministically sort them.

Bug: 78569026
Change-Id: I4b9e8f36b533f4dd1eb288753dbefdbfb08ab464
diff --git a/src/main/java/com/android/tools/r8/code/Format10t.java b/src/main/java/com/android/tools/r8/code/Format10t.java
index 4c61fa3..8365a28 100644
--- a/src/main/java/com/android/tools/r8/code/Format10t.java
+++ b/src/main/java/com/android/tools/r8/code/Format10t.java
@@ -4,6 +4,7 @@
 package com.android.tools.r8.code;
 
 import com.android.tools.r8.dex.IndexedItemCollection;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.ObjectToOffsetMapping;
 import com.android.tools.r8.naming.ClassNameMapper;
 import java.nio.ShortBuffer;
@@ -53,7 +54,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     // No references.
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/Format10x.java b/src/main/java/com/android/tools/r8/code/Format10x.java
index 8eed571..0b497fb 100644
--- a/src/main/java/com/android/tools/r8/code/Format10x.java
+++ b/src/main/java/com/android/tools/r8/code/Format10x.java
@@ -4,6 +4,7 @@
 package com.android.tools.r8.code;
 
 import com.android.tools.r8.dex.IndexedItemCollection;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.ObjectToOffsetMapping;
 import com.android.tools.r8.naming.ClassNameMapper;
 import java.nio.ShortBuffer;
@@ -45,7 +46,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     // No references.
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/Format11n.java b/src/main/java/com/android/tools/r8/code/Format11n.java
index f2b8ac2..4d9a01b 100644
--- a/src/main/java/com/android/tools/r8/code/Format11n.java
+++ b/src/main/java/com/android/tools/r8/code/Format11n.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.dex.IndexedItemCollection;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.ObjectToOffsetMapping;
 import com.android.tools.r8.naming.ClassNameMapper;
 import java.nio.ShortBuffer;
@@ -58,7 +59,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     // No references.
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/Format11x.java b/src/main/java/com/android/tools/r8/code/Format11x.java
index 318bf04..dd5a76b 100644
--- a/src/main/java/com/android/tools/r8/code/Format11x.java
+++ b/src/main/java/com/android/tools/r8/code/Format11x.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.dex.IndexedItemCollection;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.ObjectToOffsetMapping;
 import com.android.tools.r8.naming.ClassNameMapper;
 import java.nio.ShortBuffer;
@@ -53,7 +54,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     // No references.
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/Format12x.java b/src/main/java/com/android/tools/r8/code/Format12x.java
index ac90623..07ec8e2 100644
--- a/src/main/java/com/android/tools/r8/code/Format12x.java
+++ b/src/main/java/com/android/tools/r8/code/Format12x.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.dex.IndexedItemCollection;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.ObjectToOffsetMapping;
 import com.android.tools.r8.naming.ClassNameMapper;
 import java.nio.ShortBuffer;
@@ -57,7 +58,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     // No references.
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/Format20t.java b/src/main/java/com/android/tools/r8/code/Format20t.java
index f145476..ee32757 100644
--- a/src/main/java/com/android/tools/r8/code/Format20t.java
+++ b/src/main/java/com/android/tools/r8/code/Format20t.java
@@ -4,6 +4,7 @@
 package com.android.tools.r8.code;
 
 import com.android.tools.r8.dex.IndexedItemCollection;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.ObjectToOffsetMapping;
 import com.android.tools.r8.naming.ClassNameMapper;
 import java.nio.ShortBuffer;
@@ -53,7 +54,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     // No references.
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/Format21c.java b/src/main/java/com/android/tools/r8/code/Format21c.java
index 2ae2808..faa9d58 100644
--- a/src/main/java/com/android/tools/r8/code/Format21c.java
+++ b/src/main/java/com/android/tools/r8/code/Format21c.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.dex.IndexedItemCollection;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.IndexedDexItem;
 import com.android.tools.r8.graph.ObjectToOffsetMapping;
 import com.android.tools.r8.naming.ClassNameMapper;
@@ -62,8 +63,9 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
-    BBBB.collectIndexedItems(indexedItems);
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
+    BBBB.collectIndexedItems(indexedItems, method, instructionOffset);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/code/Format21h.java b/src/main/java/com/android/tools/r8/code/Format21h.java
index 221dc9e..074a0a0 100644
--- a/src/main/java/com/android/tools/r8/code/Format21h.java
+++ b/src/main/java/com/android/tools/r8/code/Format21h.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.dex.IndexedItemCollection;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.ObjectToOffsetMapping;
 import java.nio.ShortBuffer;
 
@@ -48,7 +49,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     // No references.
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/Format21s.java b/src/main/java/com/android/tools/r8/code/Format21s.java
index a9d7dc1..48f457c 100644
--- a/src/main/java/com/android/tools/r8/code/Format21s.java
+++ b/src/main/java/com/android/tools/r8/code/Format21s.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.dex.IndexedItemCollection;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.ObjectToOffsetMapping;
 import com.android.tools.r8.naming.ClassNameMapper;
 import com.android.tools.r8.utils.StringUtils;
@@ -60,7 +61,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     // No references.
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/Format21t.java b/src/main/java/com/android/tools/r8/code/Format21t.java
index 9f15752..40b7227 100644
--- a/src/main/java/com/android/tools/r8/code/Format21t.java
+++ b/src/main/java/com/android/tools/r8/code/Format21t.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.dex.IndexedItemCollection;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.ObjectToOffsetMapping;
 import com.android.tools.r8.ir.code.If.Type;
 import com.android.tools.r8.ir.code.ValueType;
@@ -76,7 +77,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     // No references.
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/Format22b.java b/src/main/java/com/android/tools/r8/code/Format22b.java
index 3952eb7..86a51b6 100644
--- a/src/main/java/com/android/tools/r8/code/Format22b.java
+++ b/src/main/java/com/android/tools/r8/code/Format22b.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.dex.IndexedItemCollection;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.ObjectToOffsetMapping;
 import com.android.tools.r8.naming.ClassNameMapper;
 import com.android.tools.r8.utils.StringUtils;
@@ -65,7 +66,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     // No references.
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/Format22c.java b/src/main/java/com/android/tools/r8/code/Format22c.java
index 6f8d6c6..16082a4 100644
--- a/src/main/java/com/android/tools/r8/code/Format22c.java
+++ b/src/main/java/com/android/tools/r8/code/Format22c.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.dex.IndexedItemCollection;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.IndexedDexItem;
 import com.android.tools.r8.graph.ObjectToOffsetMapping;
 import com.android.tools.r8.naming.ClassNameMapper;
@@ -66,8 +67,9 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
-    CCCC.collectIndexedItems(indexedItems);
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
+    CCCC.collectIndexedItems(indexedItems, method, instructionOffset);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/code/Format22s.java b/src/main/java/com/android/tools/r8/code/Format22s.java
index 25c51d6..9666b21 100644
--- a/src/main/java/com/android/tools/r8/code/Format22s.java
+++ b/src/main/java/com/android/tools/r8/code/Format22s.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.dex.IndexedItemCollection;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.ObjectToOffsetMapping;
 import com.android.tools.r8.naming.ClassNameMapper;
 import com.android.tools.r8.utils.StringUtils;
@@ -65,7 +66,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     // No references.
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/Format22t.java b/src/main/java/com/android/tools/r8/code/Format22t.java
index 9bf727c..ae05622 100644
--- a/src/main/java/com/android/tools/r8/code/Format22t.java
+++ b/src/main/java/com/android/tools/r8/code/Format22t.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.dex.IndexedItemCollection;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.ObjectToOffsetMapping;
 import com.android.tools.r8.ir.code.If.Type;
 import com.android.tools.r8.ir.code.ValueType;
@@ -82,7 +83,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     // No references.
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/Format22x.java b/src/main/java/com/android/tools/r8/code/Format22x.java
index 5c1b2c4..d30f023 100644
--- a/src/main/java/com/android/tools/r8/code/Format22x.java
+++ b/src/main/java/com/android/tools/r8/code/Format22x.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.dex.IndexedItemCollection;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.ObjectToOffsetMapping;
 import com.android.tools.r8.naming.ClassNameMapper;
 import java.nio.ShortBuffer;
@@ -59,7 +60,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     // No references.
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/Format23x.java b/src/main/java/com/android/tools/r8/code/Format23x.java
index 739b66f..02722db 100644
--- a/src/main/java/com/android/tools/r8/code/Format23x.java
+++ b/src/main/java/com/android/tools/r8/code/Format23x.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.dex.IndexedItemCollection;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.ObjectToOffsetMapping;
 import com.android.tools.r8.naming.ClassNameMapper;
 import java.nio.ShortBuffer;
@@ -63,7 +64,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     // No references.
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/Format30t.java b/src/main/java/com/android/tools/r8/code/Format30t.java
index bfcf0d3..5ef18eb 100644
--- a/src/main/java/com/android/tools/r8/code/Format30t.java
+++ b/src/main/java/com/android/tools/r8/code/Format30t.java
@@ -4,6 +4,7 @@
 package com.android.tools.r8.code;
 
 import com.android.tools.r8.dex.IndexedItemCollection;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.ObjectToOffsetMapping;
 import com.android.tools.r8.naming.ClassNameMapper;
 import java.nio.ShortBuffer;
@@ -52,7 +53,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     // No references.
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/Format31c.java b/src/main/java/com/android/tools/r8/code/Format31c.java
index ead4920..3019b9b 100644
--- a/src/main/java/com/android/tools/r8/code/Format31c.java
+++ b/src/main/java/com/android/tools/r8/code/Format31c.java
@@ -6,6 +6,7 @@
 import static com.android.tools.r8.dex.Constants.U8BIT_MAX;
 
 import com.android.tools.r8.dex.IndexedItemCollection;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.graph.IndexedDexItem;
 import com.android.tools.r8.graph.ObjectToOffsetMapping;
@@ -58,8 +59,9 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
-    BBBBBBBB.collectIndexedItems(indexedItems);
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
+    BBBBBBBB.collectIndexedItems(indexedItems, method, instructionOffset);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/code/Format31i.java b/src/main/java/com/android/tools/r8/code/Format31i.java
index 5e55ca4..192b28d 100644
--- a/src/main/java/com/android/tools/r8/code/Format31i.java
+++ b/src/main/java/com/android/tools/r8/code/Format31i.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.dex.IndexedItemCollection;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.ObjectToOffsetMapping;
 import com.android.tools.r8.naming.ClassNameMapper;
 import java.nio.ShortBuffer;
@@ -53,7 +54,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     // No references.
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/Format31t.java b/src/main/java/com/android/tools/r8/code/Format31t.java
index d650fed..19de81f 100644
--- a/src/main/java/com/android/tools/r8/code/Format31t.java
+++ b/src/main/java/com/android/tools/r8/code/Format31t.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.dex.IndexedItemCollection;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.ObjectToOffsetMapping;
 import com.android.tools.r8.naming.ClassNameMapper;
 import java.nio.ShortBuffer;
@@ -68,7 +69,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     // No references.
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/Format32x.java b/src/main/java/com/android/tools/r8/code/Format32x.java
index a31a494..4c70702 100644
--- a/src/main/java/com/android/tools/r8/code/Format32x.java
+++ b/src/main/java/com/android/tools/r8/code/Format32x.java
@@ -6,6 +6,7 @@
 import static com.android.tools.r8.dex.Constants.U16BIT_MAX;
 
 import com.android.tools.r8.dex.IndexedItemCollection;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.ObjectToOffsetMapping;
 import com.android.tools.r8.naming.ClassNameMapper;
 import java.nio.ShortBuffer;
@@ -61,7 +62,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     // No references.
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/Format35c.java b/src/main/java/com/android/tools/r8/code/Format35c.java
index b1f3f49..f8c68c3 100644
--- a/src/main/java/com/android/tools/r8/code/Format35c.java
+++ b/src/main/java/com/android/tools/r8/code/Format35c.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.dex.IndexedItemCollection;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.IndexedDexItem;
 import com.android.tools.r8.graph.ObjectToOffsetMapping;
 import com.android.tools.r8.naming.ClassNameMapper;
@@ -110,8 +111,9 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
-    BBBB.collectIndexedItems(indexedItems);
+  public void collectIndexedItems(
+      IndexedItemCollection indexedItems, DexMethod method, int instructionOffset) {
+    BBBB.collectIndexedItems(indexedItems, method, instructionOffset);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/code/Format3rc.java b/src/main/java/com/android/tools/r8/code/Format3rc.java
index 4362b4e..77d3571 100644
--- a/src/main/java/com/android/tools/r8/code/Format3rc.java
+++ b/src/main/java/com/android/tools/r8/code/Format3rc.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.dex.IndexedItemCollection;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.IndexedDexItem;
 import com.android.tools.r8.graph.ObjectToOffsetMapping;
 import com.android.tools.r8.naming.ClassNameMapper;
@@ -88,8 +89,9 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
-    BBBB.collectIndexedItems(indexedItems);
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
+    BBBB.collectIndexedItems(indexedItems, method, instructionOffset);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/code/Format45cc.java b/src/main/java/com/android/tools/r8/code/Format45cc.java
index f5123cf..fc88461 100644
--- a/src/main/java/com/android/tools/r8/code/Format45cc.java
+++ b/src/main/java/com/android/tools/r8/code/Format45cc.java
@@ -87,9 +87,10 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
-    BBBB.collectIndexedItems(indexedItems);
-    HHHH.collectIndexedItems(indexedItems);
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
+    BBBB.collectIndexedItems(indexedItems, method, instructionOffset);
+    HHHH.collectIndexedItems(indexedItems, method, instructionOffset);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/code/Format4rcc.java b/src/main/java/com/android/tools/r8/code/Format4rcc.java
index 0ec2780..c139b03 100644
--- a/src/main/java/com/android/tools/r8/code/Format4rcc.java
+++ b/src/main/java/com/android/tools/r8/code/Format4rcc.java
@@ -93,9 +93,10 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
-    BBBB.collectIndexedItems(indexedItems);
-    HHHH.collectIndexedItems(indexedItems);
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
+    BBBB.collectIndexedItems(indexedItems, method, instructionOffset);
+    HHHH.collectIndexedItems(indexedItems, method, instructionOffset);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/code/Format51l.java b/src/main/java/com/android/tools/r8/code/Format51l.java
index 0e9ad93..008e724 100644
--- a/src/main/java/com/android/tools/r8/code/Format51l.java
+++ b/src/main/java/com/android/tools/r8/code/Format51l.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.dex.IndexedItemCollection;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.ObjectToOffsetMapping;
 import com.android.tools.r8.naming.ClassNameMapper;
 import java.nio.ShortBuffer;
@@ -53,7 +54,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     // No references.
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/Instruction.java b/src/main/java/com/android/tools/r8/code/Instruction.java
index 154622b..09d5671b 100644
--- a/src/main/java/com/android/tools/r8/code/Instruction.java
+++ b/src/main/java/com/android/tools/r8/code/Instruction.java
@@ -239,7 +239,8 @@
 
   public abstract void write(ShortBuffer buffer, ObjectToOffsetMapping mapping);
 
-  public abstract void collectIndexedItems(IndexedItemCollection indexedItems);
+  public abstract void collectIndexedItems(
+      IndexedItemCollection indexedItems, DexMethod method, int instructionOffset);
 
   public boolean equals(Instruction other, BiPredicate<IndexedDexItem, IndexedDexItem> equality) {
     // In the default case, there is nothing to substitute.
diff --git a/src/main/java/com/android/tools/r8/graph/Code.java b/src/main/java/com/android/tools/r8/graph/Code.java
index 08d65f0..db9306d 100644
--- a/src/main/java/com/android/tools/r8/graph/Code.java
+++ b/src/main/java/com/android/tools/r8/graph/Code.java
@@ -77,7 +77,8 @@
   }
 
   @Override
-  void collectIndexedItems(IndexedItemCollection collection) {
+  void collectIndexedItems(IndexedItemCollection collection,
+      DexMethod method, int instructionOffset) {
     throw new Unreachable();
   }
 
diff --git a/src/main/java/com/android/tools/r8/graph/DexAnnotation.java b/src/main/java/com/android/tools/r8/graph/DexAnnotation.java
index d762340..73ac7fb 100644
--- a/src/main/java/com/android/tools/r8/graph/DexAnnotation.java
+++ b/src/main/java/com/android/tools/r8/graph/DexAnnotation.java
@@ -55,8 +55,9 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
-    annotation.collectIndexedItems(indexedItems);
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
+    annotation.collectIndexedItems(indexedItems, method, instructionOffset);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/graph/DexAnnotationDirectory.java b/src/main/java/com/android/tools/r8/graph/DexAnnotationDirectory.java
index db55cd6..aa5d145 100644
--- a/src/main/java/com/android/tools/r8/graph/DexAnnotationDirectory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexAnnotationDirectory.java
@@ -98,7 +98,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection collection) {
+  public void collectIndexedItems(IndexedItemCollection collection,
+      DexMethod method, int instructionOffset) {
     throw new Unreachable();
   }
 
diff --git a/src/main/java/com/android/tools/r8/graph/DexAnnotationElement.java b/src/main/java/com/android/tools/r8/graph/DexAnnotationElement.java
index c55ea05..040d256 100644
--- a/src/main/java/com/android/tools/r8/graph/DexAnnotationElement.java
+++ b/src/main/java/com/android/tools/r8/graph/DexAnnotationElement.java
@@ -39,9 +39,10 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
-    name.collectIndexedItems(indexedItems);
-    value.collectIndexedItems(indexedItems);
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
+    name.collectIndexedItems(indexedItems, method, instructionOffset);
+    value.collectIndexedItems(indexedItems, method, instructionOffset);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/graph/DexAnnotationSet.java b/src/main/java/com/android/tools/r8/graph/DexAnnotationSet.java
index 93e103d..9ee8fba 100644
--- a/src/main/java/com/android/tools/r8/graph/DexAnnotationSet.java
+++ b/src/main/java/com/android/tools/r8/graph/DexAnnotationSet.java
@@ -39,7 +39,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     collectAll(indexedItems, annotations);
   }
 
diff --git a/src/main/java/com/android/tools/r8/graph/DexAnnotationSetRefList.java b/src/main/java/com/android/tools/r8/graph/DexAnnotationSetRefList.java
index e6b4a2c..4bb1314 100644
--- a/src/main/java/com/android/tools/r8/graph/DexAnnotationSetRefList.java
+++ b/src/main/java/com/android/tools/r8/graph/DexAnnotationSetRefList.java
@@ -50,7 +50,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     collectAll(indexedItems, values);
   }
 
diff --git a/src/main/java/com/android/tools/r8/graph/DexCallSite.java b/src/main/java/com/android/tools/r8/graph/DexCallSite.java
index c193134..e690317 100644
--- a/src/main/java/com/android/tools/r8/graph/DexCallSite.java
+++ b/src/main/java/com/android/tools/r8/graph/DexCallSite.java
@@ -21,7 +21,7 @@
 import org.objectweb.asm.Opcodes;
 import org.objectweb.asm.tree.InvokeDynamicInsnNode;
 
-public final class DexCallSite extends IndexedDexItem {
+public final class DexCallSite extends IndexedDexItem implements Comparable<DexCallSite> {
 
   public final DexString methodName;
   public final DexProto methodProto;
@@ -31,6 +31,11 @@
 
   private DexEncodedArray encodedArray = null;
 
+  // Only used for sorting for deterministic output. This is the method and the instruction
+  // offset where this DexCallSite ends up in the output.
+  private DexMethod method;
+  private int instructionOffset;
+
   DexCallSite(
       DexString methodName,
       DexProto methodProto,
@@ -110,13 +115,18 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
+    assert method != null;
     if (indexedItems.addCallSite(this)) {
-      methodName.collectIndexedItems(indexedItems);
-      methodProto.collectIndexedItems(indexedItems);
-      bootstrapMethod.collectIndexedItems(indexedItems);
+      assert this.method == null;
+      this.method = method;
+      this.instructionOffset = instructionOffset;
+      methodName.collectIndexedItems(indexedItems, method, instructionOffset);
+      methodProto.collectIndexedItems(indexedItems, method, instructionOffset);
+      bootstrapMethod.collectIndexedItems(indexedItems, method, instructionOffset);
       for (DexValue arg : bootstrapArgs) {
-        arg.collectIndexedItems(indexedItems);
+        arg.collectIndexedItems(indexedItems, method, instructionOffset);
       }
     }
   }
@@ -141,6 +151,17 @@
     return new HashBuilder().build();
   }
 
+  @Override
+  public int compareTo(DexCallSite other) {
+    assert method != null && other.method != null;
+    int methodCompare = method.slowCompareTo(other.method);
+    if (methodCompare != 0) {
+      return methodCompare;
+    }
+    assert (instructionOffset - other.instructionOffset) != 0;
+    return instructionOffset - other.instructionOffset;
+  }
+
   private final class HashBuilder {
     private ByteArrayOutputStream bytes;
     private ObjectOutputStream out;
diff --git a/src/main/java/com/android/tools/r8/graph/DexClasspathClass.java b/src/main/java/com/android/tools/r8/graph/DexClasspathClass.java
index 4308dd4..27bb976 100644
--- a/src/main/java/com/android/tools/r8/graph/DexClasspathClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexClasspathClass.java
@@ -50,7 +50,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     throw new Unreachable();
   }
 
diff --git a/src/main/java/com/android/tools/r8/graph/DexCode.java b/src/main/java/com/android/tools/r8/graph/DexCode.java
index 50117c7..a023357 100644
--- a/src/main/java/com/android/tools/r8/graph/DexCode.java
+++ b/src/main/java/com/android/tools/r8/graph/DexCode.java
@@ -336,9 +336,11 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(
+      IndexedItemCollection indexedItems, DexMethod method, int instructionOffset) {
+    assert instructionOffset == -1;
     for (Instruction insn : instructions) {
-      insn.collectIndexedItems(indexedItems);
+      insn.collectIndexedItems(indexedItems, method, insn.getOffset());
     }
     if (debugInfo != null) {
       debugInfo.collectIndexedItems(indexedItems);
@@ -417,7 +419,8 @@
     }
 
     @Override
-    void collectIndexedItems(IndexedItemCollection indexedItems) {
+    void collectIndexedItems(IndexedItemCollection indexedItems,
+        DexMethod method, int instructionOffset) {
       // Intentionally left empty.
     }
 
@@ -462,7 +465,8 @@
     }
 
     @Override
-    public void collectIndexedItems(IndexedItemCollection indexedItems) {
+    public void collectIndexedItems(IndexedItemCollection indexedItems,
+        DexMethod method, int instructionOffset) {
       collectAll(indexedItems, pairs);
     }
 
@@ -503,8 +507,9 @@
       }
 
       @Override
-      public void collectIndexedItems(IndexedItemCollection indexedItems) {
-        type.collectIndexedItems(indexedItems);
+      public void collectIndexedItems(IndexedItemCollection indexedItems,
+          DexMethod method, int instructionOffset) {
+        type.collectIndexedItems(indexedItems, method, instructionOffset);
       }
 
       @Override
diff --git a/src/main/java/com/android/tools/r8/graph/DexDebugEvent.java b/src/main/java/com/android/tools/r8/graph/DexDebugEvent.java
index 35108bd..1264a26 100644
--- a/src/main/java/com/android/tools/r8/graph/DexDebugEvent.java
+++ b/src/main/java/com/android/tools/r8/graph/DexDebugEvent.java
@@ -13,7 +13,8 @@
 abstract public class DexDebugEvent extends DexItem {
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection collection) {
+  public void collectIndexedItems(IndexedItemCollection collection,
+      DexMethod method, int instructionOffset) {
     // Empty by default.
   }
 
@@ -212,15 +213,16 @@
     }
 
     @Override
-    public void collectIndexedItems(IndexedItemCollection collection) {
+    public void collectIndexedItems(IndexedItemCollection collection,
+        DexMethod method, int instructionOffset) {
       if (name != null) {
-        name.collectIndexedItems(collection);
+        name.collectIndexedItems(collection, method, instructionOffset);
       }
       if (type != null) {
-        type.collectIndexedItems(collection);
+        type.collectIndexedItems(collection, method, instructionOffset);
       }
       if (signature != null) {
-        signature.collectIndexedItems(collection);
+        signature.collectIndexedItems(collection, method, instructionOffset);
       }
     }
 
@@ -351,8 +353,9 @@
     }
 
     @Override
-    public void collectIndexedItems(IndexedItemCollection collection) {
-      fileName.collectIndexedItems(collection);
+    public void collectIndexedItems(IndexedItemCollection collection,
+        DexMethod method, int instructionOffset) {
+      fileName.collectIndexedItems(collection, method, instructionOffset);
     }
 
     @Override
diff --git a/src/main/java/com/android/tools/r8/graph/DexDebugInfo.java b/src/main/java/com/android/tools/r8/graph/DexDebugInfo.java
index 4b8c4b8..9c27243 100644
--- a/src/main/java/com/android/tools/r8/graph/DexDebugInfo.java
+++ b/src/main/java/com/android/tools/r8/graph/DexDebugInfo.java
@@ -55,7 +55,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection collection) {
+  public void collectIndexedItems(IndexedItemCollection collection,
+      DexMethod method, int instructionOffset) {
     collectAll(collection, parameters);
     collectAll(collection, events);
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexEncodedAnnotation.java b/src/main/java/com/android/tools/r8/graph/DexEncodedAnnotation.java
index a8f41d6..c47e72b 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedAnnotation.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedAnnotation.java
@@ -22,8 +22,9 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
-    type.collectIndexedItems(indexedItems);
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
+    type.collectIndexedItems(indexedItems, method, instructionOffset);
     collectAll(indexedItems, elements);
   }
 
diff --git a/src/main/java/com/android/tools/r8/graph/DexEncodedArray.java b/src/main/java/com/android/tools/r8/graph/DexEncodedArray.java
index 8d7eba9..fac96c9 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedArray.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedArray.java
@@ -16,7 +16,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     collectAll(indexedItems, values);
   }
 
diff --git a/src/main/java/com/android/tools/r8/graph/DexEncodedField.java b/src/main/java/com/android/tools/r8/graph/DexEncodedField.java
index a28dc82..7083b9f 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedField.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedField.java
@@ -29,11 +29,12 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
-    field.collectIndexedItems(indexedItems);
-    annotations.collectIndexedItems(indexedItems);
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
+    field.collectIndexedItems(indexedItems, method, instructionOffset);
+    annotations.collectIndexedItems(indexedItems, method, instructionOffset);
     if (accessFlags.isStatic()) {
-      getStaticValue().collectIndexedItems(indexedItems);
+      getStaticValue().collectIndexedItems(indexedItems, method, instructionOffset);
     }
   }
 
diff --git a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
index d437180..d6bde0b 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
@@ -261,10 +261,11 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
-    method.collectIndexedItems(indexedItems);
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
+    this.method.collectIndexedItems(indexedItems);
     if (code != null) {
-      code.collectIndexedItems(indexedItems);
+      code.collectIndexedItems(indexedItems, this.method);
     }
     annotations.collectIndexedItems(indexedItems);
     parameterAnnotations.collectIndexedItems(indexedItems);
diff --git a/src/main/java/com/android/tools/r8/graph/DexField.java b/src/main/java/com/android/tools/r8/graph/DexField.java
index ab0d654..98c523d 100644
--- a/src/main/java/com/android/tools/r8/graph/DexField.java
+++ b/src/main/java/com/android/tools/r8/graph/DexField.java
@@ -48,11 +48,13 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     if (indexedItems.addField(this)) {
-      clazz.collectIndexedItems(indexedItems);
-      type.collectIndexedItems(indexedItems);
-      indexedItems.getRenamedName(this).collectIndexedItems(indexedItems);
+      clazz.collectIndexedItems(indexedItems, method, instructionOffset);
+      type.collectIndexedItems(indexedItems, method, instructionOffset);
+      indexedItems.getRenamedName(this).collectIndexedItems(
+          indexedItems, method, instructionOffset);
     }
   }
 
diff --git a/src/main/java/com/android/tools/r8/graph/DexItem.java b/src/main/java/com/android/tools/r8/graph/DexItem.java
index 88665e9..3dc5558 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItem.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItem.java
@@ -38,7 +38,16 @@
     }
   }
 
-  abstract void collectIndexedItems(IndexedItemCollection collection);
+  abstract void collectIndexedItems(IndexedItemCollection collection,
+      DexMethod method, int instructionOffset);
+
+  public void collectIndexedItems(IndexedItemCollection collection) {
+    collectIndexedItems(collection, null, -1);
+  }
+
+  public void collectIndexedItems(IndexedItemCollection collection, DexMethod method) {
+    collectIndexedItems(collection, method, -1);
+  }
 
   abstract void collectMixedSectionItems(MixedSectionCollection collection);
 
diff --git a/src/main/java/com/android/tools/r8/graph/DexItemBasedString.java b/src/main/java/com/android/tools/r8/graph/DexItemBasedString.java
index 14fc568..36f0907 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemBasedString.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemBasedString.java
@@ -40,7 +40,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     // This instance should not exist when collecting indexed items.
     // {@link com.android.tools.r8.naming.IdentifierMinifier} will replace this with an appropriate
     // {@link DexString}.
diff --git a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
index 6b99724..d45402d 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -40,9 +40,9 @@
   private final ConcurrentHashMap<DexField, DexField> fields = new ConcurrentHashMap<>();
   private final ConcurrentHashMap<DexProto, DexProto> protos = new ConcurrentHashMap<>();
   private final ConcurrentHashMap<DexMethod, DexMethod> methods = new ConcurrentHashMap<>();
-  private final ConcurrentHashMap<DexCallSite, DexCallSite> callSites = new ConcurrentHashMap<>();
   private final ConcurrentHashMap<DexMethodHandle, DexMethodHandle> methodHandles =
       new ConcurrentHashMap<>();
+  private final List<DexCallSite> callSites = new ArrayList<>();
 
   // DexDebugEvent Canonicalization.
   private final Int2ObjectMap<AdvanceLine> advanceLines = new Int2ObjectOpenHashMap<>();
@@ -611,9 +611,13 @@
   public DexCallSite createCallSite(
       DexString methodName, DexProto methodProto,
       DexMethodHandle bootstrapMethod, List<DexValue> bootstrapArgs) {
+    // Call sites are never equal and therefore we do not canonicalize.
     assert !sorted;
     DexCallSite callSite = new DexCallSite(methodName, methodProto, bootstrapMethod, bootstrapArgs);
-    return canonicalize(callSites, callSite);
+    synchronized (callSites) {
+      callSites.add(callSite);
+    }
+    return callSite;
   }
 
   public DexMethod createMethod(DexString clazzDescriptor, DexString name,
@@ -727,7 +731,7 @@
     new ArrayList<>(types.values()).forEach(f);
   }
 
-  public void forAllCallSites(Consumer<DexCallSite> f) {
-    new ArrayList<>(callSites.values()).forEach(f);
+  synchronized public void forAllCallSites(Consumer<DexCallSite> f) {
+    new ArrayList<>(callSites).forEach(f);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/graph/DexLibraryClass.java b/src/main/java/com/android/tools/r8/graph/DexLibraryClass.java
index 0fac5e8..5e25fa9 100644
--- a/src/main/java/com/android/tools/r8/graph/DexLibraryClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexLibraryClass.java
@@ -55,7 +55,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     throw new Unreachable();
   }
 
diff --git a/src/main/java/com/android/tools/r8/graph/DexMemberAnnotation.java b/src/main/java/com/android/tools/r8/graph/DexMemberAnnotation.java
index 6f959c7..f005588 100644
--- a/src/main/java/com/android/tools/r8/graph/DexMemberAnnotation.java
+++ b/src/main/java/com/android/tools/r8/graph/DexMemberAnnotation.java
@@ -17,9 +17,10 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
-    item.collectIndexedItems(indexedItems);
-    annotations.collectIndexedItems(indexedItems);
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
+    item.collectIndexedItems(indexedItems, method, instructionOffset);
+    annotations.collectIndexedItems(indexedItems, method, instructionOffset);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/graph/DexMethod.java b/src/main/java/com/android/tools/r8/graph/DexMethod.java
index 9c3e9a5..f1acdac 100644
--- a/src/main/java/com/android/tools/r8/graph/DexMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexMethod.java
@@ -40,11 +40,13 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     if (indexedItems.addMethod(this)) {
-      holder.collectIndexedItems(indexedItems);
-      proto.collectIndexedItems(indexedItems);
-      indexedItems.getRenamedName(this).collectIndexedItems(indexedItems);
+      holder.collectIndexedItems(indexedItems, method, instructionOffset);
+      proto.collectIndexedItems(indexedItems, method, instructionOffset);
+      indexedItems.getRenamedName(this).collectIndexedItems(
+          indexedItems, method, instructionOffset);
     }
   }
 
diff --git a/src/main/java/com/android/tools/r8/graph/DexMethodHandle.java b/src/main/java/com/android/tools/r8/graph/DexMethodHandle.java
index a9e3b8e..06ea28d 100644
--- a/src/main/java/com/android/tools/r8/graph/DexMethodHandle.java
+++ b/src/main/java/com/android/tools/r8/graph/DexMethodHandle.java
@@ -206,9 +206,10 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     if (indexedItems.addMethodHandle(this)) {
-      fieldOrMethod.collectIndexedItems(indexedItems);
+      fieldOrMethod.collectIndexedItems(indexedItems, method, instructionOffset);
     }
   }
 
@@ -289,7 +290,7 @@
 
   @Override
   public int compareTo(DexMethodHandle other) {
-    return sortedCompareTo(other.getSortedIndex());
+    return slowCompareTo(other);
   }
 
   public Handle toAsmHandle(NamingLens lens) {
diff --git a/src/main/java/com/android/tools/r8/graph/DexProgramClass.java b/src/main/java/com/android/tools/r8/graph/DexProgramClass.java
index 1473191..c1b843f 100644
--- a/src/main/java/com/android/tools/r8/graph/DexProgramClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexProgramClass.java
@@ -111,22 +111,23 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     if (indexedItems.addClass(this)) {
-      type.collectIndexedItems(indexedItems);
+      type.collectIndexedItems(indexedItems, method, instructionOffset);
       if (superType != null) {
-        superType.collectIndexedItems(indexedItems);
+        superType.collectIndexedItems(indexedItems, method, instructionOffset);
       } else {
         assert type.toDescriptorString().equals("Ljava/lang/Object;");
       }
       if (sourceFile != null) {
-        sourceFile.collectIndexedItems(indexedItems);
+        sourceFile.collectIndexedItems(indexedItems, method, instructionOffset);
       }
       if (annotations != null) {
-        annotations.collectIndexedItems(indexedItems);
+        annotations.collectIndexedItems(indexedItems, method, instructionOffset);
       }
       if (interfaces != null) {
-        interfaces.collectIndexedItems(indexedItems);
+        interfaces.collectIndexedItems(indexedItems, method, instructionOffset);
       }
       if (getEnclosingMethod() != null) {
         getEnclosingMethod().collectIndexedItems(indexedItems);
diff --git a/src/main/java/com/android/tools/r8/graph/DexProto.java b/src/main/java/com/android/tools/r8/graph/DexProto.java
index 7acab73..17f6efa 100644
--- a/src/main/java/com/android/tools/r8/graph/DexProto.java
+++ b/src/main/java/com/android/tools/r8/graph/DexProto.java
@@ -42,11 +42,12 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     if (indexedItems.addProto(this)) {
-      shorty.collectIndexedItems(indexedItems);
-      returnType.collectIndexedItems(indexedItems);
-      parameters.collectIndexedItems(indexedItems);
+      shorty.collectIndexedItems(indexedItems, method, instructionOffset);
+      returnType.collectIndexedItems(indexedItems, method, instructionOffset);
+      parameters.collectIndexedItems(indexedItems, method, instructionOffset);
     }
   }
 
diff --git a/src/main/java/com/android/tools/r8/graph/DexString.java b/src/main/java/com/android/tools/r8/graph/DexString.java
index 3127422..12587f4 100644
--- a/src/main/java/com/android/tools/r8/graph/DexString.java
+++ b/src/main/java/com/android/tools/r8/graph/DexString.java
@@ -139,7 +139,8 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection indexedItems) {
+  public void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     indexedItems.addString(this);
   }
 
diff --git a/src/main/java/com/android/tools/r8/graph/DexType.java b/src/main/java/com/android/tools/r8/graph/DexType.java
index 3d0a177..d178e4a 100644
--- a/src/main/java/com/android/tools/r8/graph/DexType.java
+++ b/src/main/java/com/android/tools/r8/graph/DexType.java
@@ -261,9 +261,11 @@
   }
 
   @Override
-  public void collectIndexedItems(IndexedItemCollection collection) {
+  public void collectIndexedItems(IndexedItemCollection collection,
+      DexMethod method, int instructionOffset) {
     if (collection.addType(this)) {
-      collection.getRenamedDescriptor(this).collectIndexedItems(collection);
+      collection.getRenamedDescriptor(this).collectIndexedItems(collection, method,
+          instructionOffset);
     }
   }
 
diff --git a/src/main/java/com/android/tools/r8/graph/DexTypeList.java b/src/main/java/com/android/tools/r8/graph/DexTypeList.java
index 5de71a1..8df5030 100644
--- a/src/main/java/com/android/tools/r8/graph/DexTypeList.java
+++ b/src/main/java/com/android/tools/r8/graph/DexTypeList.java
@@ -34,9 +34,10 @@
   }
 
   @Override
-  void collectIndexedItems(IndexedItemCollection indexedItems) {
+  void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset) {
     for (DexType type : values) {
-      type.collectIndexedItems(indexedItems);
+      type.collectIndexedItems(indexedItems, method, instructionOffset);
     }
   }
 
diff --git a/src/main/java/com/android/tools/r8/graph/DexValue.java b/src/main/java/com/android/tools/r8/graph/DexValue.java
index 342ea2a..ed99d25 100644
--- a/src/main/java/com/android/tools/r8/graph/DexValue.java
+++ b/src/main/java/com/android/tools/r8/graph/DexValue.java
@@ -153,7 +153,8 @@
     }
 
     @Override
-    public void collectIndexedItems(IndexedItemCollection indexedItems) {
+    public void collectIndexedItems(IndexedItemCollection indexedItems,
+        DexMethod method, int instructionOffset) {
       throw new Unreachable();
     }
 
@@ -206,7 +207,8 @@
   static private abstract class SimpleDexValue extends DexValue {
 
     @Override
-    public void collectIndexedItems(IndexedItemCollection indexedItems) {
+    public void collectIndexedItems(IndexedItemCollection indexedItems,
+        DexMethod method, int instructionOffset) {
       // Intentionally left empty
     }
 
@@ -662,8 +664,9 @@
     }
 
     @Override
-    public void collectIndexedItems(IndexedItemCollection indexedItems) {
-      value.collectIndexedItems(indexedItems);
+    public void collectIndexedItems(IndexedItemCollection indexedItems,
+        DexMethod method, int instructionOffset) {
+      value.collectIndexedItems(indexedItems, method, instructionOffset);
     }
 
     @Override
@@ -727,8 +730,9 @@
     }
 
     @Override
-    public void collectIndexedItems(IndexedItemCollection indexedItems) {
-      value.collectIndexedItems(indexedItems);
+    public void collectIndexedItems(IndexedItemCollection indexedItems,
+        DexMethod method, int instructionOffset) {
+      value.collectIndexedItems(indexedItems, method, instructionOffset);
     }
   }
 
@@ -744,8 +748,9 @@
     }
 
     @Override
-    public void collectIndexedItems(IndexedItemCollection indexedItems) {
-      value.collectIndexedItems(indexedItems);
+    public void collectIndexedItems(IndexedItemCollection indexedItems,
+        DexMethod method, int instructionOffset) {
+      value.collectIndexedItems(indexedItems, method, instructionOffset);
     }
   }
 
@@ -761,8 +766,9 @@
     }
 
     @Override
-    public void collectIndexedItems(IndexedItemCollection indexedItems) {
-      value.collectIndexedItems(indexedItems);
+    public void collectIndexedItems(IndexedItemCollection indexedItems,
+        DexMethod method, int instructionOffset) {
+      value.collectIndexedItems(indexedItems, method, instructionOffset);
     }
   }
 
@@ -778,8 +784,9 @@
     }
 
     @Override
-    public void collectIndexedItems(IndexedItemCollection indexedItems) {
-      value.collectIndexedItems(indexedItems);
+    public void collectIndexedItems(IndexedItemCollection indexedItems,
+        DexMethod method, int instructionOffset) {
+      value.collectIndexedItems(indexedItems, method, instructionOffset);
     }
   }
 
@@ -795,8 +802,9 @@
     }
 
     @Override
-    public void collectIndexedItems(IndexedItemCollection indexedItems) {
-      value.collectIndexedItems(indexedItems);
+    public void collectIndexedItems(IndexedItemCollection indexedItems,
+        DexMethod method, int instructionOffset) {
+      value.collectIndexedItems(indexedItems, method, instructionOffset);
     }
   }
 
@@ -813,7 +821,8 @@
     }
 
     @Override
-    public void collectIndexedItems(IndexedItemCollection indexedItems) {
+    public void collectIndexedItems(IndexedItemCollection indexedItems,
+        DexMethod method, int instructionOffset) {
       collectAll(indexedItems, values);
     }
 
@@ -875,8 +884,9 @@
     }
 
     @Override
-    public void collectIndexedItems(IndexedItemCollection indexedItems) {
-      value.collectIndexedItems(indexedItems);
+    public void collectIndexedItems(IndexedItemCollection indexedItems,
+        DexMethod method, int instructionOffset) {
+      value.collectIndexedItems(indexedItems, method, instructionOffset);
     }
 
     @Override
@@ -1041,8 +1051,9 @@
     }
 
     @Override
-    public void collectIndexedItems(IndexedItemCollection indexedItems) {
-      value.collectIndexedItems(indexedItems);
+    public void collectIndexedItems(IndexedItemCollection indexedItems,
+        DexMethod method, int instructionOffset) {
+      value.collectIndexedItems(indexedItems, method, instructionOffset);
     }
   }
 }
diff --git a/src/main/java/com/android/tools/r8/graph/IndexedDexItem.java b/src/main/java/com/android/tools/r8/graph/IndexedDexItem.java
index e45a7c7..0ee9b42 100644
--- a/src/main/java/com/android/tools/r8/graph/IndexedDexItem.java
+++ b/src/main/java/com/android/tools/r8/graph/IndexedDexItem.java
@@ -15,7 +15,8 @@
   private int sortedIndex = SORTED_INDEX_UNKNOWN; // assigned globally after reading.
 
   @Override
-  public abstract void collectIndexedItems(IndexedItemCollection indexedItems);
+  public abstract void collectIndexedItems(IndexedItemCollection indexedItems,
+      DexMethod method, int instructionOffset);
 
   @Override
   void collectMixedSectionItems(MixedSectionCollection mixedItems) {
diff --git a/src/main/java/com/android/tools/r8/graph/ObjectToOffsetMapping.java b/src/main/java/com/android/tools/r8/graph/ObjectToOffsetMapping.java
index a8b431c..5cbdf26 100644
--- a/src/main/java/com/android/tools/r8/graph/ObjectToOffsetMapping.java
+++ b/src/main/java/com/android/tools/r8/graph/ObjectToOffsetMapping.java
@@ -52,16 +52,13 @@
     assert methodHandles != null;
 
     this.classes = sortClasses(application, classes);
-    this.protos = createMap(protos, true, this::failOnOverflow);
-    this.types = createMap(types, true, this::failOnOverflow);
-    this.methods = createMap(methods, true, this::failOnOverflow);
-    this.fields = createMap(fields, true, this::failOnOverflow);
-    this.strings = createMap(strings, true, this::setFirstJumboString);
-    // No need to sort CallSite, they will be written in data section in the callSites order,
-    // consequently offset of call site used into the call site section will be in ascending order.
-    this.callSites = createMap(callSites, false, this::failOnOverflow);
-    // No need to sort method handle
-    this.methodHandles = createMap(methodHandles, false, this::failOnOverflow);
+    this.protos = createMap(protos, this::failOnOverflow);
+    this.types = createMap(types, this::failOnOverflow);
+    this.methods = createMap(methods, this::failOnOverflow);
+    this.fields = createMap(fields, this::failOnOverflow);
+    this.strings = createMap(strings, this::setFirstJumboString);
+    this.callSites = createMap(callSites, this::failOnOverflow);
+    this.methodHandles = createMap(methodHandles, this::failOnOverflow);
   }
 
   private void setFirstJumboString(DexString string) {
@@ -74,13 +71,13 @@
   }
 
   private <T extends IndexedDexItem> Reference2IntMap<T> createMap(Collection<T> items,
-      boolean sort, Consumer<T> onUInt16Overflow) {
+      Consumer<T> onUInt16Overflow) {
     if (items.isEmpty()) {
       return null;
     }
     Reference2IntMap<T> map = new Reference2IntLinkedOpenHashMap<>(items.size());
     map.defaultReturnValue(NOT_FOUND);
-    Collection<T> sorted = sort ? items.stream().sorted().collect(Collectors.toList()) : items;
+    Collection<T> sorted = items.stream().sorted().collect(Collectors.toList());
     int index = 0;
     for (T item : sorted) {
       if (index == Constants.U16BIT_MAX + 1) {