diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index 812fec2..7c7e830 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.28";
+  public static final String LABEL = "1.3.29";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
index 00d8bdf..b9818ad 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
@@ -291,9 +291,10 @@
     }
   }
 
-  private void staticizeClasses(OptimizationFeedback feedback) {
+  private void staticizeClasses(OptimizationFeedback feedback, ExecutorService executorService)
+      throws ExecutionException {
     if (classStaticizer != null) {
-      classStaticizer.staticizeCandidates(feedback);
+      classStaticizer.staticizeCandidates(feedback, executorService);
     }
   }
 
@@ -494,9 +495,10 @@
     // Build a new application with jumbo string info.
     Builder<?> builder = application.builder();
     builder.setHighestSortingString(highestSortingString);
-    // b/112831361
+
+    // TODO(b/112831361): Implement support for staticizeClasses in CF backend.
     if (!options.isGeneratingClassFiles()) {
-      staticizeClasses(directFeedback);
+      staticizeClasses(directFeedback, executorService);
     }
 
     // Second inlining pass for dealing with double inline callers.
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/staticizer/ClassStaticizer.java b/src/main/java/com/android/tools/r8/ir/optimize/staticizer/ClassStaticizer.java
index e33d977..711f63a 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/staticizer/ClassStaticizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/staticizer/ClassStaticizer.java
@@ -35,6 +35,8 @@
 import java.util.Map;
 import java.util.Set;
 import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
 import java.util.concurrent.atomic.AtomicBoolean;
 import java.util.concurrent.atomic.AtomicInteger;
 import java.util.concurrent.atomic.AtomicReference;
@@ -526,9 +528,10 @@
   //  2. Rewrite instance methods of classes being staticized into static ones
   //  3. Rewrite methods referencing staticized members, also remove instance creation
   //
-  public final void staticizeCandidates(OptimizationFeedback feedback) {
+  public final void staticizeCandidates(
+      OptimizationFeedback feedback, ExecutorService executorService) throws ExecutionException {
     phase = Phase.None; // We are done with processing/examining methods.
-    new StaticizingProcessor(this).run(feedback);
+    new StaticizingProcessor(this, executorService).run(feedback);
   }
 
   public final void fixupMethodCode(DexEncodedMethod method, IRCode code) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/staticizer/StaticizingProcessor.java b/src/main/java/com/android/tools/r8/ir/optimize/staticizer/StaticizingProcessor.java
index b7c830f..18a9920 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/staticizer/StaticizingProcessor.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/staticizer/StaticizingProcessor.java
@@ -28,6 +28,7 @@
 import com.android.tools.r8.ir.conversion.OptimizationFeedback;
 import com.android.tools.r8.ir.optimize.Outliner;
 import com.android.tools.r8.ir.optimize.staticizer.ClassStaticizer.CandidateInfo;
+import com.android.tools.r8.utils.ThreadUtils;
 import com.google.common.collect.BiMap;
 import com.google.common.collect.HashBiMap;
 import com.google.common.collect.Sets;
@@ -40,12 +41,17 @@
 import java.util.Map;
 import java.util.Map.Entry;
 import java.util.Set;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Future;
 import java.util.function.BiConsumer;
 import java.util.stream.Collectors;
 import java.util.stream.Stream;
 
 final class StaticizingProcessor {
+
   private final ClassStaticizer classStaticizer;
+  private final ExecutorService executorService;
 
   private final Set<DexEncodedMethod> referencingExtraMethods = Sets.newIdentityHashSet();
   private final Map<DexEncodedMethod, CandidateInfo> hostClassInits = new IdentityHashMap<>();
@@ -53,35 +59,36 @@
   private final Map<DexField, CandidateInfo> singletonFields = new IdentityHashMap<>();
   private final Map<DexType, DexType> candidateToHostMapping = new IdentityHashMap<>();
 
-  StaticizingProcessor(ClassStaticizer classStaticizer) {
+  StaticizingProcessor(ClassStaticizer classStaticizer, ExecutorService executorService) {
     this.classStaticizer = classStaticizer;
+    this.executorService = executorService;
   }
 
-  final void run(OptimizationFeedback feedback) {
-    // Filter out candidates based on the information we collected
-    // while examining methods.
+  final void run(OptimizationFeedback feedback) throws ExecutionException {
+    // Filter out candidates based on the information we collected while examining methods.
     finalEligibilityCheck();
 
     // Prepare interim data.
     prepareCandidates();
 
     // Process all host class initializers (only remove instantiations).
-    processMethods(hostClassInits.keySet().stream(), this::removeCandidateInstantiation, feedback);
+    processMethodsConcurrently(
+        hostClassInits.keySet(), this::removeCandidateInstantiation, feedback);
 
     // Process instance methods to be staticized (only remove references to 'this').
-    processMethods(methodsToBeStaticized.stream(), this::removeReferencesToThis, feedback);
+    processMethodsConcurrently(methodsToBeStaticized, this::removeReferencesToThis, feedback);
 
     // Convert instance methods into static methods with an extra parameter.
     Set<DexEncodedMethod> staticizedMethods = staticizeMethodSymbols();
 
-    // Process all other methods that may reference singleton fields
-    // and call methods on them. (Note that we exclude the former instance methods,
-    // but include new static methods created as a result of staticizing.
-    Stream<DexEncodedMethod> methods = Streams.concat(
-        referencingExtraMethods.stream(),
-        staticizedMethods.stream(),
-        hostClassInits.keySet().stream());
-    processMethods(methods, this::rewriteReferences, feedback);
+    // Process all other methods that may reference singleton fields and call methods on them.
+    // (Note that we exclude the former instance methods, but include new static methods created as
+    // a result of staticizing.)
+    Set<DexEncodedMethod> methods = Sets.newIdentityHashSet();
+    methods.addAll(referencingExtraMethods);
+    methods.addAll(staticizedMethods);
+    methods.addAll(hostClassInits.keySet());
+    processMethodsConcurrently(methods, this::rewriteReferences, feedback);
   }
 
   private void finalEligibilityCheck() {
@@ -165,12 +172,39 @@
     referencingExtraMethods.removeAll(removedInstanceMethods);
   }
 
-  private void processMethods(Stream<DexEncodedMethod> methods,
-      BiConsumer<DexEncodedMethod, IRCode> strategy, OptimizationFeedback feedback) {
+  /**
+   * Processes the given methods concurrently using the given strategy.
+   *
+   * <p>Note that, when the strategy {@link #rewriteReferences(DexEncodedMethod, IRCode)} is being
+   * applied, it is important that we never inline a method from `methods` which has still not been
+   * reprocessed. This could lead to broken code, because the strategy that rewrites the broken
+   * references is applied *before* inlining (because the broken references in the inlinee are never
+   * rewritten). We currently avoid this situation by processing all the methods concurrently
+   * (inlining of a method that is processed concurrently is not allowed).
+   */
+  private void processMethodsConcurrently(
+      Set<DexEncodedMethod> methods,
+      BiConsumer<DexEncodedMethod, IRCode> strategy,
+      OptimizationFeedback feedback)
+      throws ExecutionException {
     classStaticizer.setFixupStrategy(strategy);
-    methods.sorted(DexEncodedMethod::slowCompare).forEach(
-        method -> classStaticizer.converter.processMethod(method, feedback,
-            x -> false, CallSiteInformation.empty(), Outliner::noProcessing));
+
+    List<Future<?>> futures = new ArrayList<>();
+    for (DexEncodedMethod method : methods) {
+      futures.add(
+          executorService.submit(
+              () -> {
+                classStaticizer.converter.processMethod(
+                    method,
+                    feedback,
+                    methods::contains,
+                    CallSiteInformation.empty(),
+                    Outliner::noProcessing);
+                return null; // we want a Callable not a Runnable to be able to throw
+              }));
+    }
+    ThreadUtils.awaitFutures(futures);
+
     classStaticizer.cleanFixupStrategy();
   }