diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index b7f1455..d394692 100644
--- a/src/main/java/com/android/tools/r8/Version.java
+++ b/src/main/java/com/android/tools/r8/Version.java
@@ -11,7 +11,7 @@
 
   // This field is accessed from release scripts using simple pattern matching.
   // Therefore, changing this field could break our release scripts.
-  public static final String LABEL = "1.3.26";
+  public static final String LABEL = "1.3.27";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/code/ConstString.java b/src/main/java/com/android/tools/r8/code/ConstString.java
index d165de5..a5733ad 100644
--- a/src/main/java/com/android/tools/r8/code/ConstString.java
+++ b/src/main/java/com/android/tools/r8/code/ConstString.java
@@ -45,6 +45,16 @@
   }
 
   @Override
+  public ConstString asConstString() {
+    return this;
+  }
+
+  @Override
+  public boolean isConstString() {
+    return true;
+  }
+
+  @Override
   public String toString(ClassNameMapper naming) {
     return formatString("v" + AA + ", \"" + BBBB.toString() + "\"");
   }
diff --git a/src/main/java/com/android/tools/r8/code/ConstStringJumbo.java b/src/main/java/com/android/tools/r8/code/ConstStringJumbo.java
index 5f4c4d8..b24f86f 100644
--- a/src/main/java/com/android/tools/r8/code/ConstStringJumbo.java
+++ b/src/main/java/com/android/tools/r8/code/ConstStringJumbo.java
@@ -42,6 +42,16 @@
   }
 
   @Override
+  public ConstStringJumbo asConstStringJumbo() {
+    return this;
+  }
+
+  @Override
+  public boolean isConstStringJumbo() {
+    return true;
+  }
+
+  @Override
   public String toString(ClassNameMapper naming) {
     return formatString("v" + AA + ", \"" + BBBBBBBB.toString() + "\"");
   }
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 c8b5154..aaf9140 100644
--- a/src/main/java/com/android/tools/r8/code/Instruction.java
+++ b/src/main/java/com/android/tools/r8/code/Instruction.java
@@ -122,6 +122,22 @@
     this.offset = offset;
   }
 
+  public ConstString asConstString() {
+    return null;
+  }
+
+  public boolean isConstString() {
+    return false;
+  }
+
+  public ConstStringJumbo asConstStringJumbo() {
+    return null;
+  }
+
+  public boolean isConstStringJumbo() {
+    return false;
+  }
+
   public boolean isSimpleNop() {
     return !isPayload() && this instanceof Nop;
   }
diff --git a/src/main/java/com/android/tools/r8/code/InstructionFactory.java b/src/main/java/com/android/tools/r8/code/InstructionFactory.java
index 40c5f6e..14d2f4b 100644
--- a/src/main/java/com/android/tools/r8/code/InstructionFactory.java
+++ b/src/main/java/com/android/tools/r8/code/InstructionFactory.java
@@ -3,7 +3,6 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.code;
 
-import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.graph.OffsetToObjectMapping;
 import java.nio.ByteBuffer;
 import java.nio.ShortBuffer;
@@ -12,8 +11,6 @@
 
 public class InstructionFactory extends BaseInstructionFactory {
 
-  private DexString highestSortingString = null;
-
   static private Instruction readFrom(ShortBufferBytecodeStream stream,
       OffsetToObjectMapping mapping) {
     int high = stream.nextByte();
@@ -33,26 +30,11 @@
     List<Instruction> insn = new ArrayList<>(length);
     while (range.hasMore()) {
       Instruction instruction = readFrom(range, mapping);
-      if (instruction instanceof ConstString) {
-        updateHighestSortingString(((ConstString) instruction).getString());
-      } else if (instruction instanceof ConstStringJumbo) {
-        updateHighestSortingString(((ConstStringJumbo) instruction).getString());
-      }
       insn.add(instruction);
     }
     return insn.toArray(new Instruction[insn.size()]);
   }
 
-  public DexString getHighestSortingString() {
-    return highestSortingString;
-  }
-
-  private void updateHighestSortingString(DexString string) {
-    if (highestSortingString == null || highestSortingString.slowCompareTo(string) < 0) {
-      highestSortingString = string;
-    }
-  }
-
   private static class ShortBufferBytecodeStream implements BytecodeStream {
 
     private final int length;
diff --git a/src/main/java/com/android/tools/r8/dex/DexParser.java b/src/main/java/com/android/tools/r8/dex/DexParser.java
index d762646..0240da5 100644
--- a/src/main/java/com/android/tools/r8/dex/DexParser.java
+++ b/src/main/java/com/android/tools/r8/dex/DexParser.java
@@ -825,15 +825,7 @@
     InstructionFactory factory = new InstructionFactory();
     Instruction[] instructions =
         factory.readSequenceFrom(ShortBuffer.wrap(code), 0, code.length, indexedItems);
-    return new DexCode(
-        registerSize,
-        insSize,
-        outsSize,
-        instructions,
-        tries,
-        handlers,
-        debugInfo,
-        factory.getHighestSortingString());
+    return new DexCode(registerSize, insSize, outsSize, instructions, tries, handlers, debugInfo);
   }
 
   void populateIndexTables() {
diff --git a/src/main/java/com/android/tools/r8/dex/JumboStringRewriter.java b/src/main/java/com/android/tools/r8/dex/JumboStringRewriter.java
index b151ef8..1c18107 100644
--- a/src/main/java/com/android/tools/r8/dex/JumboStringRewriter.java
+++ b/src/main/java/com/android/tools/r8/dex/JumboStringRewriter.java
@@ -120,18 +120,20 @@
     TryHandler[] newHandlers = rewriteHandlerOffsets();
     DexDebugInfo newDebugInfo = rewriteDebugInfoOffsets();
     // Set the new code on the method.
-    DexCode code = method.getCode().asDexCode();
+    DexCode oldCode = method.getCode().asDexCode();
+    DexCode newCode =
+        new DexCode(
+            oldCode.registerSize,
+            oldCode.incomingRegisterSize,
+            oldCode.outgoingRegisterSize,
+            newInstructions.toArray(new Instruction[newInstructions.size()]),
+            newTries,
+            newHandlers,
+            newDebugInfo);
     // As we have rewritten the code, we now know that its highest string index that is not
     // a jumbo-string is firstJumboString (actually the previous string, but we do not have that).
-    method.setCode(new DexCode(
-        code.registerSize,
-        code.incomingRegisterSize,
-        code.outgoingRegisterSize,
-        newInstructions.toArray(new Instruction[newInstructions.size()]),
-        newTries,
-        newHandlers,
-        newDebugInfo,
-        firstJumboString));
+    newCode.highestSortingString = firstJumboString;
+    method.setCode(newCode);
   }
 
   private void rewriteInstructionOffsets(List<Instruction> instructions) {
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 4b52a9e..8d37b45 100644
--- a/src/main/java/com/android/tools/r8/graph/DexCode.java
+++ b/src/main/java/com/android/tools/r8/graph/DexCode.java
@@ -38,7 +38,7 @@
   public final TryHandler[] handlers;
   public final Instruction[] instructions;
 
-  public final DexString highestSortingString;
+  public DexString highestSortingString;
   private DexDebugInfo debugInfo;
 
   public DexCode(
@@ -48,8 +48,7 @@
       Instruction[] instructions,
       Try[] tries,
       TryHandler[] handlers,
-      DexDebugInfo debugInfo,
-      DexString highestSortingString) {
+      DexDebugInfo debugInfo) {
     this.incomingRegisterSize = insSize;
     this.registerSize = registerSize;
     this.outgoingRegisterSize = outsSize;
@@ -57,7 +56,6 @@
     this.tries = tries;
     this.handlers = handlers;
     this.debugInfo = debugInfo;
-    this.highestSortingString = highestSortingString;
     hashCode();  // Cache the hash code eagerly.
   }
 
@@ -68,8 +66,14 @@
     // by 1, it becomes just a regular register which is never used, and thus will be
     // gone when we build an IR from this code. Rebuilding IR for methods 'staticized'
     // this way is highly recommended to improve register allocation.
-    return new DexCode(registerSize, incomingRegisterSize - 1, outgoingRegisterSize,
-        instructions, tries, handlers, debugInfoWithoutFirstParameter(), highestSortingString);
+    return new DexCode(
+        registerSize,
+        incomingRegisterSize - 1,
+        outgoingRegisterSize,
+        instructions,
+        tries,
+        handlers,
+        debugInfoWithoutFirstParameter());
   }
 
   @Override
@@ -371,8 +375,14 @@
   public void collectIndexedItems(
       IndexedItemCollection indexedItems, DexMethod method, int instructionOffset) {
     assert instructionOffset == -1;
+    highestSortingString = null;
     for (Instruction insn : instructions) {
       insn.collectIndexedItems(indexedItems, method, insn.getOffset());
+      if (insn.isConstString()) {
+        updateHighestSortingString(insn.asConstString().getString());
+      } else if (insn.isConstStringJumbo()) {
+        updateHighestSortingString(insn.asConstStringJumbo().getString());
+      }
     }
     if (debugInfo != null) {
       debugInfo.collectIndexedItems(indexedItems);
@@ -384,6 +394,14 @@
     }
   }
 
+  private void updateHighestSortingString(DexString candidate) {
+    assert candidate != null;
+    assert !(candidate instanceof DexItemBasedString);
+    if (highestSortingString == null || highestSortingString.slowCompareTo(candidate) < 0) {
+      highestSortingString = candidate;
+    }
+  }
+
   public boolean usesExceptionHandling() {
     return tries.length != 0;
   }
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 bca0395..c3db796 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
@@ -492,9 +492,14 @@
     for (DexType type : method.proto.parameters.values) {
       requiredArgRegisters += ValueType.fromDexType(type).requiredRegisters();
     }
-    // Passing null as highestSortingString is save, as ConstString instructions are not allowed.
-    return new DexCode(Math.max(numberOfRegisters, requiredArgRegisters), requiredArgRegisters,
-        outRegisters, instructions, new DexCode.Try[0], new DexCode.TryHandler[0], null, null);
+    return new DexCode(
+        Math.max(numberOfRegisters, requiredArgRegisters),
+        requiredArgRegisters,
+        outRegisters,
+        instructions,
+        new DexCode.Try[0],
+        new DexCode.TryHandler[0],
+        null);
   }
 
   public DexEncodedMethod toEmptyThrowingMethodDex() {
@@ -674,9 +679,13 @@
     DexString firstJumboString = null;
     if (force) {
       firstJumboString = mapping.getFirstString();
-    } else if (code.highestSortingString != null
-        && mapping.getOffsetFor(code.highestSortingString) > Constants.MAX_NON_JUMBO_INDEX) {
-      firstJumboString = mapping.getFirstJumboString();
+    } else {
+      assert code.highestSortingString != null
+          || Arrays.stream(code.instructions).noneMatch(Instruction::isConstString);
+      if (code.highestSortingString != null
+          && mapping.getOffsetFor(code.highestSortingString) > Constants.MAX_NON_JUMBO_INDEX) {
+        firstJumboString = mapping.getFirstJumboString();
+      }
     }
     if (firstJumboString != null) {
       JumboStringRewriter rewriter =
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 34f850e..3a23ed8 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemBasedString.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemBasedString.java
@@ -7,6 +7,8 @@
 import com.android.tools.r8.errors.Unreachable;
 import java.util.Arrays;
 
+// TODO(b/117828645): Introduce a DexItemBasedConstString instruction instead, as the use of
+// DexItemBasedString implies that we cannot rely on DexStrings being canonicalized.
 public class DexItemBasedString extends DexString {
   public final DexReference basedOn;
 
diff --git a/src/main/java/com/android/tools/r8/ir/code/ConstString.java b/src/main/java/com/android/tools/r8/ir/code/ConstString.java
index f2ecc89..ee160dc 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ConstString.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ConstString.java
@@ -36,7 +36,6 @@
 
   @Override
   public void buildDex(DexBuilder builder) {
-    builder.registerStringReference(value);
     int dest = builder.allocatedRegister(dest(), getNumber());
     builder.add(this, new com.android.tools.r8.code.ConstString(dest, value));
   }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/DexBuilder.java b/src/main/java/com/android/tools/r8/ir/conversion/DexBuilder.java
index 1f7a684..4e11690 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/DexBuilder.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/DexBuilder.java
@@ -42,7 +42,6 @@
 import com.android.tools.r8.graph.DexCode.TryHandler.TypeAddrPair;
 import com.android.tools.r8.graph.DexDebugEventBuilder;
 import com.android.tools.r8.graph.DexItemFactory;
-import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.code.Argument;
 import com.android.tools.r8.ir.code.BasicBlock;
@@ -108,9 +107,6 @@
   private int inRegisterCount = 0;
   private int outRegisterCount = 0;
 
-  // The string reference in the code with the highest index.
-  private DexString highestSortingReferencedString = null;
-
   // Whether or not the generated code has a backwards branch.
   private boolean hasBackwardsBranch = false;
 
@@ -136,7 +132,6 @@
     instructionToInfo = new Info[instructionNumberToIndex(ir.numberRemainingInstructions())];
     inRegisterCount = 0;
     outRegisterCount = 0;
-    highestSortingReferencedString = null;
     nextBlock = null;
   }
 
@@ -258,15 +253,15 @@
     TryInfo tryInfo = computeTryInfo();
 
     // Return the dex code.
-    DexCode code = new DexCode(
-        registerAllocator.registersUsed(),
-        inRegisterCount,
-        outRegisterCount,
-        dexInstructions.toArray(new Instruction[dexInstructions.size()]),
-        tryInfo.tries,
-        tryInfo.handlers,
-        debugEventBuilder.build(),
-        highestSortingReferencedString);
+    DexCode code =
+        new DexCode(
+            registerAllocator.registersUsed(),
+            inRegisterCount,
+            outRegisterCount,
+            dexInstructions.toArray(new Instruction[dexInstructions.size()]),
+            tryInfo.tries,
+            tryInfo.handlers,
+            debugEventBuilder.build());
 
     return code;
   }
@@ -399,13 +394,6 @@
     ifsNeedingRewrite.add(block);
   }
 
-  public void registerStringReference(DexString string) {
-    if (highestSortingReferencedString == null
-        || string.slowCompareTo(highestSortingReferencedString) > 0) {
-      highestSortingReferencedString = string;
-    }
-  }
-
   public void requestOutgoingRegisters(int requiredRegisterCount) {
     if (requiredRegisterCount > outRegisterCount) {
       outRegisterCount = requiredRegisterCount;
diff --git a/src/test/java/com/android/tools/r8/dex/JumboStringProcessing.java b/src/test/java/com/android/tools/r8/dex/JumboStringProcessing.java
index 3b1e30a..e11b957 100644
--- a/src/test/java/com/android/tools/r8/dex/JumboStringProcessing.java
+++ b/src/test/java/com/android/tools/r8/dex/JumboStringProcessing.java
@@ -156,7 +156,6 @@
         instructions,
         new Try[0],
         null,
-        null,
         null);
     MethodAccessFlags flags = MethodAccessFlags.fromSharedAccessFlags(Constants.ACC_PUBLIC, false);
     DexEncodedMethod method = new DexEncodedMethod(null, flags, null, null, code);
diff --git a/src/test/java/com/android/tools/r8/dex/SharedClassWritingTest.java b/src/test/java/com/android/tools/r8/dex/SharedClassWritingTest.java
index a518a36..d672f75 100644
--- a/src/test/java/com/android/tools/r8/dex/SharedClassWritingTest.java
+++ b/src/test/java/com/android/tools/r8/dex/SharedClassWritingTest.java
@@ -78,8 +78,7 @@
       instructions[i] = new ConstString(0, strings[startOffset + i]);
     }
     instructions[stringCount] = new ReturnVoid();
-    DexCode code = new DexCode(1, 0, 0, instructions, new Try[0], new TryHandler[0], null,
-        strings[startOffset + stringCount - 1]);
+    DexCode code = new DexCode(1, 0, 0, instructions, new Try[0], new TryHandler[0], null);
     return new DexEncodedMethod(
         dexItemFactory.createMethod(
             holder, dexItemFactory.createProto(dexItemFactory.voidType), "theMethod"),