--- a/js/src/jit/WarpOracle.cpp
+++ b/js/src/jit/WarpOracle.cpp
@@ -37,16 +37,20 @@ using namespace js::jit;
 // inlined.
 class MOZ_STACK_CLASS WarpScriptOracle {
   JSContext* cx_;
   WarpOracle* oracle_;
   MIRGenerator& mirGen_;
   TempAllocator& alloc_;
   HandleScript script_;
 
+  // Index of the next ICEntry for getICEntry. This assumes the script's
+  // bytecode is processed from first to last instruction.
+  uint32_t icEntryIndex_ = 0;
+
   template <typename... Args>
   mozilla::GenericErrorResult<AbortReason> abort(Args&&... args) {
     return oracle_->abort(script_, args...);
   }
 
   AbortReasonOr<WarpEnvironment> createEnvironment();
   AbortReasonOr<Ok> maybeInlineIC(WarpOpSnapshotList& snapshots,
                                   BytecodeLocation loc);
@@ -55,16 +59,18 @@ class MOZ_STACK_CLASS WarpScriptOracle {
   WarpScriptOracle(JSContext* cx, WarpOracle* oracle, HandleScript script)
       : cx_(cx),
         oracle_(oracle),
         mirGen_(oracle->mirGen()),
         alloc_(mirGen_.alloc()),
         script_(script) {}
 
   AbortReasonOr<WarpScriptSnapshot*> createScriptSnapshot();
+
+  const ICEntry& getICEntry(BytecodeLocation loc);
 };
 
 WarpOracle::WarpOracle(JSContext* cx, MIRGenerator& mirGen,
                        HandleScript outerScript)
     : cx_(cx),
       mirGen_(mirGen),
       alloc_(mirGen.alloc()),
       outerScript_(outerScript) {}
@@ -150,16 +156,29 @@ static MOZ_MUST_USE bool AddWarpGetImpor
   // check.
   bool needsLexicalCheck =
       targetEnv->getSlot(slot).isMagic(JS_UNINITIALIZED_LEXICAL);
 
   return AddOpSnapshot<WarpGetImport>(alloc, snapshots, offset, targetEnv,
                                       numFixedSlots, slot, needsLexicalCheck);
 }
 
+const ICEntry& WarpScriptOracle::getICEntry(BytecodeLocation loc) {
+  const uint32_t offset = loc.bytecodeToOffset(script_);
+
+  const ICEntry* entry;
+  do {
+    entry = &script_->jitScript()->icEntry(icEntryIndex_);
+    icEntryIndex_++;
+  } while (entry->pcOffset() < offset);
+
+  MOZ_ASSERT(entry->pcOffset() == offset);
+  return *entry;
+}
+
 AbortReasonOr<WarpEnvironment> WarpScriptOracle::createEnvironment() {
   // Don't do anything if the script doesn't use the environment chain.
   // Always make an environment chain if the script needs an arguments object
   // because ArgumentsObject construction requires the environment chain to be
   // passed in.
   if (!script_->jitScript()->usesEnvironmentChain() &&
       !script_->needsArgsObj()) {
     return WarpEnvironment(NoEnvironment());
@@ -411,30 +430,27 @@ AbortReasonOr<WarpScriptSnapshot*> WarpS
             return abort(AbortReason::Error);
           }
           instrumentationScriptId.emplace(id);
         }
         break;
       }
 
       case JSOp::Rest: {
-        const ICEntry& entry =
-            script_->jitScript()->icEntryFromPCOffset(offset);
+        const ICEntry& entry = getICEntry(loc);
         ICRest_Fallback* stub = entry.fallbackStub()->toRest_Fallback();
         if (!AddOpSnapshot<WarpRest>(alloc_, opSnapshots, offset,
                                      stub->templateObject())) {
           return abort(AbortReason::Alloc);
         }
         break;
       }
 
       case JSOp::NewArray: {
-        // TODO: optimize ICEntry lookup.
-        const ICEntry& entry =
-            script_->jitScript()->icEntryFromPCOffset(offset);
+        const ICEntry& entry = getICEntry(loc);
         auto* stub = entry.fallbackStub()->toNewArray_Fallback();
         if (ArrayObject* templateObj = stub->templateObject()) {
           // Only inline elements are supported without a VM call.
           size_t numInlineElements =
               gc::GetGCKindSlots(templateObj->asTenured().getAllocKind()) -
               ObjectElements::VALUES_PER_HEADER;
           bool useVMCall = loc.getNewArrayLength() > numInlineElements;
           if (!AddOpSnapshot<WarpNewArray>(alloc_, opSnapshots, offset,
@@ -443,19 +459,17 @@ AbortReasonOr<WarpScriptSnapshot*> WarpS
           }
         }
         break;
       }
 
       case JSOp::NewObject:
       case JSOp::NewObjectWithGroup:
       case JSOp::NewInit: {
-        // TODO: optimize ICEntry lookup.
-        const ICEntry& entry =
-            script_->jitScript()->icEntryFromPCOffset(offset);
+        const ICEntry& entry = getICEntry(loc);
         auto* stub = entry.fallbackStub()->toNewObject_Fallback();
         if (JSObject* templateObj = stub->templateObject()) {
           if (!AddOpSnapshot<WarpNewObject>(alloc_, opSnapshots, offset,
                                             templateObj)) {
             return abort(AbortReason::Alloc);
           }
         }
         break;
@@ -691,21 +705,17 @@ static void LineNumberAndColumn(HandleSc
 
 AbortReasonOr<Ok> WarpScriptOracle::maybeInlineIC(WarpOpSnapshotList& snapshots,
                                                   BytecodeLocation loc) {
   // Add a WarpCacheIR snapshot if the Baseline IC has a single ICStub we can
   // inline.
 
   MOZ_ASSERT(loc.opHasIC());
 
-  uint32_t offset = loc.bytecodeToOffset(script_);
-
-  // TODO: slow. Should traverse ICEntries as we go, like BaselineCompiler.
-  const ICEntry& entry = script_->jitScript()->icEntryFromPCOffset(offset);
-
+  const ICEntry& entry = getICEntry(loc);
   ICStub* stub = entry.firstStub();
 
   if (stub->isFallback()) {
     [[maybe_unused]] unsigned line, column;
     LineNumberAndColumn(script_, loc, &line, &column);
 
     // No optimized stubs.
     JitSpew(JitSpew_WarpTranspiler,
@@ -823,15 +833,16 @@ AbortReasonOr<Ok> WarpScriptOracle::mayb
   }
 
   // We don't need any GC barriers because the stub data does not contain
   // nursery pointers (checked above) so we can do a bitwise copy.
   std::copy_n(stubData, bytesNeeded, stubDataCopy);
 
   JitCode* jitCode = stub->jitCode();
 
+  uint32_t offset = loc.bytecodeToOffset(script_);
   if (!AddOpSnapshot<WarpCacheIR>(alloc_, snapshots, offset, jitCode, stubInfo,
                                   stubDataCopy)) {
     return abort(AbortReason::Alloc);
   }
 
   return Ok();
 }