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 d01e231..1df3aef 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
@@ -137,6 +137,7 @@
 import java.util.HashSet;
 import java.util.IdentityHashMap;
 import java.util.LinkedHashMap;
+import java.util.LinkedHashSet;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.ListIterator;
@@ -1842,7 +1843,7 @@
     // TODO(ager): Generalize this to shorten live ranges for more instructions? Currently
     // doing so seems to make things worse.
     LazyBox<DominatorTree> dominatorTreeMemoization = new LazyBox<>(() -> new DominatorTree(code));
-    Map<BasicBlock, Map<Value, Instruction>> addConstantInBlock = new IdentityHashMap<>();
+    Map<BasicBlock, LinkedHashMap<Value, Instruction>> addConstantInBlock = new IdentityHashMap<>();
     LinkedList<BasicBlock> blocks = code.blocks;
     for (BasicBlock block : blocks) {
       if (block == blocks.getFirst()) {
@@ -1852,9 +1853,7 @@
             block,
             dominatorTreeMemoization,
             addConstantInBlock,
-            insn ->
-                (insn.isConstNumber() && insn.outValue().hasAnyUsers())
-                    || (insn.isConstString() && insn.outValue().hasAnyUsers()));
+            insn -> insn.isConstNumber() || insn.isConstString());
       } else {
         // For all following blocks only process ConstString with just one use.
         shortenLiveRangesInsideBlock(
@@ -1871,7 +1870,7 @@
 
     // Process all blocks in stable order to avoid non-determinism of hash map iterator.
     for (BasicBlock block : blocks) {
-      Map<Value, Instruction> constants = addConstantInBlock.get(block);
+      LinkedHashMap<Value, Instruction> constants = addConstantInBlock.get(block);
       if (constants == null) {
         continue;
       }
@@ -1880,7 +1879,6 @@
       if (block != blocks.getFirst() && constants.size() > STOP_SHARED_CONSTANT_THRESHOLD) {
         // If there are too many constants in the same block, they are copied rather than shared
         // except if they are used by phi instructions or they are a string constants.
-        assert constants instanceof LinkedHashMap;
         for (Instruction constantInstruction : constants.values()) {
           if (!constantInstruction.outValue().hasPhiUsers()
               && !constantInstruction.isConstString()) {
@@ -1948,68 +1946,69 @@
       IRCode code,
       BasicBlock block,
       LazyBox<DominatorTree> dominatorTreeMemoization,
-      Map<BasicBlock, Map<Value, Instruction>> addConstantInBlock,
-      Predicate<ConstInstruction> selector) {
+      Map<BasicBlock, LinkedHashMap<Value, Instruction>> addConstantInBlock,
+      Predicate<Instruction> selector) {
     InstructionListIterator iterator = block.listIterator(code);
     while (iterator.hasNext()) {
-      Instruction next = iterator.next();
-      if (!next.isConstInstruction()) {
+      Instruction instruction = iterator.next();
+      if (!instruction.isConstInstruction()
+          || instruction.hasUnusedOutValue()
+          || instruction.outValue().hasLocalInfo()) {
         continue;
       }
 
       // We don't want to push const string instructions down into code that has monitors since
       // we may attach catch handlers that are not catch-all when inlining. This is symmetric in how
       // we don't do const string canonicalization.
-      if ((next.isConstString() || next.isDexItemBasedConstString())
+      if ((instruction.isConstString() || instruction.isDexItemBasedConstString())
           && code.metadata().mayHaveMonitorInstruction()) {
         continue;
       }
 
-      ConstInstruction instruction = next.asConstInstruction();
-      if (!selector.test(instruction) || instruction.outValue().hasLocalInfo()) {
+      if (!selector.test(instruction)) {
         continue;
       }
-      Set<Instruction> uniqueUsers = instruction.outValue().uniqueUsers();
-      // Here we try to stop wasting time in the common case of large array of constants creation.
-      // We do not want to move a high number of constants up just to move them down because it
-      // takes multiple seconds in some cases (ZoneName clinit for instance).
-      // In array creation, the pattern is something like:
+
+      // Here we try to stop wasting time in the common case where constants are used immediately
+      // after their definition.
+      //
+      // This is especially important for the creation of large arrays, which has the following code
+      // pattern repeated many times, where the two loaded constants are only used by the ArrayPut
+      // instruction.
+      //
       //   Const number (the array index)
       //   Const (the array entry value)
       //   ArrayPut
-      // And both constants are used only in the put. The heuristic is therefore to check for
-      // constants used only once if the use is within the next two instructions, and only swap
-      // them if that is the case (cannot shorten the live range anyway).
-      // This heuristic drops down the time spent in large array of constant creation in
-      // shortenLiveRanges from multiple seconds to multiple milliseconds.
-      if (uniqueUsers.size() == 1 && instruction.outValue().uniquePhiUsers().size() == 0) {
-        Instruction uniqueUse = uniqueUsers.iterator().next();
-        if (iterator.hasNext()) {
-          Instruction nextNext = iterator.next();
-          if (uniqueUse == nextNext && nextNext.isArrayPut()) {
-            assert !uniqueUse.isConstInstruction();
+      //
+      // The heuristic is therefore to check for constants used only once if the use is within the
+      // next two instructions, and only swap them if that is the case (cannot shorten the live
+      // range anyway).
+      if (instruction.outValue().hasSingleUniqueUser() && !instruction.outValue().hasPhiUsers()) {
+        Instruction uniqueUse = instruction.outValue().singleUniqueUser();
+        Instruction next = iterator.next();
+        if (uniqueUse == next) {
+          continue;
+        }
+        if (next.hasOutValue()
+            && next.outValue().hasSingleUniqueUser()
+            && !next.outValue().hasPhiUsers()
+            && iterator.hasNext()) {
+          Instruction nextNext = iterator.peekNext();
+          Instruction uniqueUseNext = next.outValue().singleUniqueUser();
+          if (uniqueUse == nextNext && uniqueUseNext == nextNext) {
             continue;
           }
-          if (nextNext.isConstInstruction()) {
-            Set<Instruction> uniqueUsersNext = nextNext.outValue().uniqueUsers();
-            if (uniqueUsersNext.size() == 1
-                && nextNext.outValue().uniquePhiUsers().size() == 0
-                && iterator.hasNext()) {
-              Instruction nextNextNext = iterator.peekNext();
-              Instruction uniqueUseNext = uniqueUsersNext.iterator().next();
-              if (uniqueUse == nextNextNext
-                  && uniqueUseNext == nextNextNext
-                  && nextNextNext.isArrayPut()) {
-                continue;
-              }
-            }
-          }
-          iterator.previous();
         }
+        iterator.previous();
+        // The call to removeOrReplaceByDebugLocalRead() at the end of this method will remove the
+        // last returned element of this iterator. Therefore, we re-read this element from the
+        // iterator.
+        iterator.previous();
+        iterator.next();
       }
       // Collect the blocks for all users of the constant.
-      List<BasicBlock> userBlocks = new LinkedList<>();
-      for (Instruction user : uniqueUsers) {
+      Set<BasicBlock> userBlocks = new LinkedHashSet<>();
+      for (Instruction user : instruction.outValue().uniqueUsers()) {
         userBlocks.add(user.getBlock());
       }
       for (Phi phi : instruction.outValue().uniquePhiUsers()) {
@@ -2050,14 +2049,15 @@
         }
       }
 
-      Map<Value, Instruction> csts =
-          addConstantInBlock.computeIfAbsent(dominator, k -> new LinkedHashMap<>());
-
       ConstInstruction copy = instruction.isConstNumber()
           ? ConstNumber.copyOf(code, instruction.asConstNumber())
           : ConstString.copyOf(code, instruction.asConstString());
       instruction.outValue().replaceUsers(copy.outValue());
-      csts.put(copy.outValue(), copy);
+      addConstantInBlock
+          .computeIfAbsent(dominator, k -> new LinkedHashMap<>())
+          .put(copy.outValue(), copy);
+      assert iterator.peekPrevious() == instruction;
+      iterator.removeOrReplaceByDebugLocalRead();
     }
   }
 
diff --git a/src/test/java/com/android/tools/r8/ir/regalloc/B140588497.java b/src/test/java/com/android/tools/r8/ir/regalloc/B140588497.java
index 20a3077..3e93e17 100644
--- a/src/test/java/com/android/tools/r8/ir/regalloc/B140588497.java
+++ b/src/test/java/com/android/tools/r8/ir/regalloc/B140588497.java
@@ -5,7 +5,7 @@
 
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
 import static org.hamcrest.MatcherAssert.assertThat;
-import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.assertEquals;
 
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
@@ -13,6 +13,8 @@
 import com.android.tools.r8.utils.codeinspector.ClassSubject;
 import com.android.tools.r8.utils.codeinspector.InstructionSubject;
 import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import it.unimi.dsi.fastutil.longs.LongArrayList;
+import it.unimi.dsi.fastutil.longs.LongList;
 import java.util.Iterator;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -46,16 +48,13 @@
 
               MethodSubject m = c.uniqueMethodWithName("invokeRangeTest");
               assertThat(m, isPresent());
-              long prev;
-              long curr = -1;
               Iterator<InstructionSubject> it =
                   m.iterateInstructions(InstructionSubject::isConstNumber);
+              LongList numbers = new LongArrayList();
               while (it.hasNext()) {
-                InstructionSubject instr = it.next();
-                prev = curr;
-                curr = instr.getConstNumber();
-                assertTrue(prev < curr);
+                numbers.add(it.next().getConstNumber());
               }
+              assertEquals(new LongArrayList(new long[] {4, 5, 0, 1, 2, 3}), numbers);
             });
   }