Index: /trunk/src/VBox/VMM/VMMAll/IEMAllInstPython.py
===================================================================
--- /trunk/src/VBox/VMM/VMMAll/IEMAllInstPython.py	(revision 102556)
+++ /trunk/src/VBox/VMM/VMMAll/IEMAllInstPython.py	(revision 102557)
@@ -3064,7 +3064,7 @@
     'IEM_MC_POP_U32':                                            (McBlock.parseMcGeneric,           True,  False, ),
     'IEM_MC_POP_U64':                                            (McBlock.parseMcGeneric,           True,  False, ),
-    'IEM_MC_PREPARE_AVX_USAGE':                                  (McBlock.parseMcGeneric,           False, False, ),
-    'IEM_MC_PREPARE_FPU_USAGE':                                  (McBlock.parseMcGeneric,           False, False, ),
-    'IEM_MC_PREPARE_SSE_USAGE':                                  (McBlock.parseMcGeneric,           False, False, ),
+    'IEM_MC_PREPARE_AVX_USAGE':                                  (McBlock.parseMcGeneric,           False, True),
+    'IEM_MC_PREPARE_FPU_USAGE':                                  (McBlock.parseMcGeneric,           False, True),
+    'IEM_MC_PREPARE_SSE_USAGE':                                  (McBlock.parseMcGeneric,           False, True),
     'IEM_MC_PUSH_FPU_RESULT':                                    (McBlock.parseMcGeneric,           True,  False, ),
     'IEM_MC_PUSH_FPU_RESULT_MEM_OP':                             (McBlock.parseMcGeneric,           True,  False, ),
Index: /trunk/src/VBox/VMM/VMMAll/IEMAllN8veRecompiler.cpp
===================================================================
--- /trunk/src/VBox/VMM/VMMAll/IEMAllN8veRecompiler.cpp	(revision 102556)
+++ /trunk/src/VBox/VMM/VMMAll/IEMAllN8veRecompiler.cpp	(revision 102557)
@@ -512,54 +512,66 @@
     AssertMsgReturn(cbReq > 32 && cbReq < _512K, ("%#x\n", cbReq), NULL);
 
-    /*
-     * Adjust the request size so it'll fit the allocator alignment/whatnot.
-     *
-     * For the RTHeapSimple allocator this means to follow the logic described
-     * in iemExecMemAllocatorGrow and attempt to allocate it from one of the
-     * existing chunks if we think we've got sufficient free memory around.
-     *
-     * While for the alternative one we just align it up to a whole unit size.
-     */
+
+    for (unsigned iIteration = 0;; iIteration++)
+    {
+        /*
+         * Adjust the request size so it'll fit the allocator alignment/whatnot.
+         *
+         * For the RTHeapSimple allocator this means to follow the logic described
+         * in iemExecMemAllocatorGrow and attempt to allocate it from one of the
+         * existing chunks if we think we've got sufficient free memory around.
+         *
+         * While for the alternative one we just align it up to a whole unit size.
+         */
 #ifdef IEMEXECMEM_USE_ALT_SUB_ALLOCATOR
-    cbReq = RT_ALIGN_32(cbReq, IEMEXECMEM_ALT_SUB_ALLOC_UNIT_SIZE);
+        cbReq = RT_ALIGN_32(cbReq, IEMEXECMEM_ALT_SUB_ALLOC_UNIT_SIZE);
 #else
-    cbReq = RT_ALIGN_32(cbReq + pExecMemAllocator->cbHeapBlockHdr, 64) - pExecMemAllocator->cbHeapBlockHdr;
-#endif
-    if (cbReq <= pExecMemAllocator->cbFree)
-    {
-        uint32_t const cChunks      = pExecMemAllocator->cChunks;
-        uint32_t const idxChunkHint = pExecMemAllocator->idxChunkHint < cChunks ? pExecMemAllocator->idxChunkHint : 0;
-        for (uint32_t idxChunk = idxChunkHint; idxChunk < cChunks; idxChunk++)
+        cbReq = RT_ALIGN_32(cbReq + pExecMemAllocator->cbHeapBlockHdr, 64) - pExecMemAllocator->cbHeapBlockHdr;
+#endif
+        if (cbReq <= pExecMemAllocator->cbFree)
         {
+            uint32_t const cChunks      = pExecMemAllocator->cChunks;
+            uint32_t const idxChunkHint = pExecMemAllocator->idxChunkHint < cChunks ? pExecMemAllocator->idxChunkHint : 0;
+            for (uint32_t idxChunk = idxChunkHint; idxChunk < cChunks; idxChunk++)
+            {
+                void *pvRet = iemExecMemAllocatorAllocInChunk(pExecMemAllocator, idxChunk, cbReq);
+                if (pvRet)
+                    return pvRet;
+            }
+            for (uint32_t idxChunk = 0; idxChunk < idxChunkHint; idxChunk++)
+            {
+                void *pvRet = iemExecMemAllocatorAllocInChunk(pExecMemAllocator, idxChunk, cbReq);
+                if (pvRet)
+                    return pvRet;
+            }
+        }
+
+        /*
+         * Can we grow it with another chunk?
+         */
+        if (pExecMemAllocator->cChunks < pExecMemAllocator->cMaxChunks)
+        {
+            int rc = iemExecMemAllocatorGrow(pVCpu, pExecMemAllocator);
+            AssertLogRelRCReturn(rc, NULL);
+
+            uint32_t const idxChunk = pExecMemAllocator->cChunks - 1;
             void *pvRet = iemExecMemAllocatorAllocInChunk(pExecMemAllocator, idxChunk, cbReq);
             if (pvRet)
                 return pvRet;
+            AssertFailed();
         }
-        for (uint32_t idxChunk = 0; idxChunk < idxChunkHint; idxChunk++)
+
+        /*
+         * Try prune native TBs once.
+         */
+        if (iIteration == 0)
+            iemTbAllocatorFreeupNativeSpace(pVCpu, cbReq / sizeof(IEMNATIVEINSTR));
+        else
         {
-            void *pvRet = iemExecMemAllocatorAllocInChunk(pExecMemAllocator, idxChunk, cbReq);
-            if (pvRet)
-                return pvRet;
+            /** @todo stats...   */
+            return NULL;
         }
     }
 
-    /*
-     * Can we grow it with another chunk?
-     */
-    if (pExecMemAllocator->cChunks < pExecMemAllocator->cMaxChunks)
-    {
-        int rc = iemExecMemAllocatorGrow(pVCpu, pExecMemAllocator);
-        AssertLogRelRCReturn(rc, NULL);
-
-        uint32_t const idxChunk = pExecMemAllocator->cChunks - 1;
-        void *pvRet = iemExecMemAllocatorAllocInChunk(pExecMemAllocator, idxChunk, cbReq);
-        if (pvRet)
-            return pvRet;
-        AssertFailed();
-    }
-
-    /* What now? Prune native translation blocks from the cache? */
-    AssertFailed();
-    return NULL;
 }
 
Index: /trunk/src/VBox/VMM/VMMAll/IEMAllThrdRecompiler.cpp
===================================================================
--- /trunk/src/VBox/VMM/VMMAll/IEMAllThrdRecompiler.cpp	(revision 102556)
+++ /trunk/src/VBox/VMM/VMMAll/IEMAllThrdRecompiler.cpp	(revision 102557)
@@ -967,5 +967,5 @@
  * function before making any TB or executable memory allocations respectively.
  */
-void iemTbAllocatorProcessDelayedFrees(PVMCPU pVCpu, PIEMTBALLOCATOR pTbAllocator)
+void iemTbAllocatorProcessDelayedFrees(PVMCPUCC pVCpu, PIEMTBALLOCATOR pTbAllocator)
 {
     PIEMTB pTb = pTbAllocator->pDelayedFreeHead;
@@ -975,5 +975,5 @@
         PIEMTB const pTbNext = pTb->pNext;
         Assert(pVCpu->iem.s.pCurTbR3 != pTb);
-        iemTbAlloctorScheduleForFree(pVCpu, pTb);
+        iemTbAllocatorFree(pVCpu, pTb);
         pTb = pTbNext;
     }
@@ -1169,4 +1169,92 @@
 }
 
+
+/**
+ * This is called when we're out of space for native TBs.
+ *
+ * This uses a variation on the pruning in iemTbAllocatorAllocSlow.
+ * The difference is that we only prune native TBs and will only free any if
+ * there are least two in a group.  The conditions under which we're called are
+ * different - there will probably be free TBs in the table when we're called.
+ * Therefore we increase the group size and max scan length, though we'll stop
+ * scanning once we've reached the requested size (@a cNeededInstrs) and freed
+ * up at least 8 TBs.
+ */
+void iemTbAllocatorFreeupNativeSpace(PVMCPUCC pVCpu, uint32_t cNeededInstrs)
+{
+    PIEMTBALLOCATOR const pTbAllocator = pVCpu->iem.s.pTbAllocatorR3;
+    AssertReturnVoid(pTbAllocator && pTbAllocator->uMagic == IEMTBALLOCATOR_MAGIC);
+
+    STAM_REL_PROFILE_START(&pTbAllocator->StatPruneNative, a);
+
+    /*
+     * Flush the delayed free list before we start freeing TBs indiscriminately.
+     */
+    iemTbAllocatorProcessDelayedFrees(pVCpu, pTbAllocator);
+
+    /*
+     * Scan and free TBs.
+     */
+    uint32_t const msNow          = pVCpu->iem.s.msRecompilerPollNow;
+    uint32_t const cTbsToPrune    = 128 * 8;
+    uint32_t const cTbsPerGroup   = 4   * 4;
+    uint32_t       cFreedTbs      = 0;
+    uint32_t       cMaxInstrs     = 0;
+    uint32_t       idxTbPruneFrom = pTbAllocator->iPruneNativeFrom & ~(uint32_t)(cTbsPerGroup - 1);
+    for (uint32_t i = 0; i < cTbsToPrune; i += cTbsPerGroup, idxTbPruneFrom += cTbsPerGroup)
+    {
+        if (idxTbPruneFrom >= pTbAllocator->cTotalTbs)
+            idxTbPruneFrom = 0;
+        uint32_t idxChunk   = IEMTBALLOC_IDX_TO_CHUNK(pTbAllocator, idxTbPruneFrom);
+        uint32_t idxInChunk = IEMTBALLOC_IDX_TO_INDEX_IN_CHUNK(pTbAllocator, idxTbPruneFrom, idxChunk);
+        PIEMTB   pTb        = &pTbAllocator->aChunks[idxChunk].paTbs[idxInChunk];
+        uint32_t cMsAge     = pTb->fFlags & IEMTB_F_TYPE_NATIVE ? msNow - pTb->msLastUsed : msNow;
+        uint8_t  cNativeTbs = (pTb->fFlags & IEMTB_F_TYPE_NATIVE) != 0;
+
+        for (uint32_t j = 1, idxChunk2 = idxChunk, idxInChunk2 = idxInChunk + 1; j < cTbsPerGroup; j++, idxInChunk2++)
+        {
+            if (idxInChunk2 < pTbAllocator->cTbsPerChunk)
+            { /* likely */ }
+            else
+            {
+                idxInChunk2 = 0;
+                idxChunk2  += 1;
+                if (idxChunk2 >= pTbAllocator->cAllocatedChunks)
+                    idxChunk2 = 0;
+            }
+            PIEMTB const pTb2 = &pTbAllocator->aChunks[idxChunk2].paTbs[idxInChunk2];
+            if (pTb2->fFlags & IEMTB_F_TYPE_NATIVE)
+            {
+                cNativeTbs += 1;
+                uint32_t const cMsAge2 = msNow - pTb2->msLastUsed;
+                if (   cMsAge2 > cMsAge
+                    || (   cMsAge2 == cMsAge
+                        && (   pTb2->cUsed < pTb->cUsed
+                            || (   pTb2->cUsed == pTb->cUsed
+                                && pTb2->Native.cInstructions > pTb->Native.cInstructions)))
+                    || !(pTb->fFlags & IEMTB_F_TYPE_NATIVE))
+                {
+                    pTb        = pTb2;
+                    idxChunk   = idxChunk2;
+                    idxInChunk = idxInChunk2;
+                    cMsAge     = cMsAge2;
+                }
+            }
+        }
+
+        /* Free the TB if we found at least two native one in this group. */
+        if (cNativeTbs >= 2)
+        {
+            cMaxInstrs = RT_MAX(cMaxInstrs, pTb->Native.cInstructions);
+            iemTbAllocatorFreeInner(pVCpu, pTbAllocator, pTb, idxChunk, idxInChunk);
+            cFreedTbs++;
+            if (cFreedTbs >= 8 && cMaxInstrs >= cNeededInstrs)
+                break;
+        }
+    }
+    pTbAllocator->iPruneNativeFrom = idxTbPruneFrom;
+
+    STAM_REL_PROFILE_STOP(&pTbAllocator->StatPruneNative, a);
+}
 
 
Index: /trunk/src/VBox/VMM/VMMR3/IEMR3.cpp
===================================================================
--- /trunk/src/VBox/VMM/VMMR3/IEMR3.cpp	(revision 102556)
+++ /trunk/src/VBox/VMM/VMMR3/IEMR3.cpp	(revision 102557)
@@ -335,4 +335,6 @@
                         "Time spent freeing up TBs when full at alloc", "/IEM/CPU%u/re/TbPruningAlloc", idCpu);
 # endif
+        STAMR3RegisterF(pVM, (void *)&pTbAllocator->StatPruneNative,    STAMTYPE_PROFILE,   STAMVISIBILITY_ALWAYS, STAMUNIT_TICKS_PER_CALL,
+                        "Time spent freeing up native TBs when out of executable memory", "/IEM/CPU%u/re/TbPruningNative", idCpu);
         STAMR3RegisterF(pVM, (void *)&pTbAllocator->cAllocatedChunks,   STAMTYPE_U16,   STAMVISIBILITY_ALWAYS, STAMUNIT_COUNT,
                         "Populated TB chunks",                          "/IEM/CPU%u/re/cTbChunks", idCpu);
Index: /trunk/src/VBox/VMM/include/IEMInternal.h
===================================================================
--- /trunk/src/VBox/VMM/include/IEMInternal.h	(revision 102556)
+++ /trunk/src/VBox/VMM/include/IEMInternal.h	(revision 102557)
@@ -1213,4 +1213,8 @@
     /** Hint about which bit to start scanning the bitmap from. */
     uint32_t        iStartHint;
+    /** Where to start pruning native TBs from when we're out of executable memory.
+     *  See iemTbAllocatorFreeupNativeSpace for details. */
+    uint32_t        iPruneNativeFrom;
+    uint32_t        uPadding;
 
     /** Statistics: Number of TB allocation calls. */
@@ -1220,4 +1224,6 @@
     /** Statistics: Time spend pruning. */
     STAMPROFILE     StatPrune;
+    /** Statistics: Time spend pruning native TBs. */
+    STAMPROFILE     StatPruneNative;
 
     /** The delayed free list (see iemTbAlloctorScheduleForFree). */
@@ -5587,5 +5593,6 @@
                               uint64_t cbInitialExec, uint64_t cbMaxExec, uint32_t cbChunkExec);
 void                iemThreadedTbObsolete(PVMCPUCC pVCpu, PIEMTB pTb, bool fSafeToFree);
-void                iemTbAllocatorProcessDelayedFrees(PVMCPU pVCpu, PIEMTBALLOCATOR pTbAllocator);
+void                iemTbAllocatorProcessDelayedFrees(PVMCPUCC pVCpu, PIEMTBALLOCATOR pTbAllocator);
+void                iemTbAllocatorFreeupNativeSpace(PVMCPUCC pVCpu, uint32_t cNeededInstrs);
 
 
