kit

commit ed5f4832cdf3eb4a5193b6a54bcde06f79ba578f
parent 6cc5c5774c44412d402a94214e98a72bc8533eaa
Author: Ryan Sepassi <rsepassi@gmail.com>
Date:   Tue, 16 Jun 2026 09:32:23 -0700

Speed up live range compression

Diffstat:
M
src/opt/pass_live.c
 | 
54
++++++++++++++++++++++++------------------------------

1 file changed, 24 insertions(+), 30 deletions(-)
diff --git a/src/opt/pass_live.c b/src/opt/pass_live.c
@@ -30,7 +30,7 @@ static int opt_bitset_grow(OptBitset* bs, u32 need_words) {
 }
 
 static void opt_bitset_trim(OptBitset* bs) {
-  u32 n = bs->nwords;
+  u32 n = bs->active_words;
   while (n && bs->words[n - 1u] == 0) --n;
   bs->active_words = n;
 }
@@ -83,24 +83,26 @@ int opt_bitset_copy(OptBitset* dst, const OptBitset* src) {
     dst->words[i] = 0;
   }
   dst->active_words = n;
-  if (n && dst->words[n - 1u] == 0) opt_bitset_trim(dst);
   return changed;
 }
 
 int opt_bitset_union(OptBitset* dst, const OptBitset* src) {
   int changed = 0;
   u32 n;
+  u32 active;
   if (!dst || !src || !src->words) return 0;
   if (src->active_words > dst->nwords &&
       !opt_bitset_grow(dst, src->active_words))
     return 0;
   n = src->active_words;
+  active = dst->active_words;
   for (u32 i = 0; i < n; ++i) {
     u64 old = dst->words[i];
     dst->words[i] |= src->words[i];
     changed |= dst->words[i] != old;
+    if (dst->words[i] && active <= i) active = i + 1u;
   }
-  if (changed) opt_bitset_trim(dst);
+  dst->active_words = active;
   return changed;
 }
 
@@ -108,19 +110,22 @@ int opt_bitset_union_and_not(OptBitset* dst, const OptBitset* src,
                              const OptBitset* not_bits) {
   int changed = 0;
   u32 n;
+  u32 active;
   if (!dst || !src || !src->words) return 0;
   if (src->active_words > dst->nwords &&
       !opt_bitset_grow(dst, src->active_words))
     return 0;
   n = src->active_words;
+  active = dst->active_words;
   for (u32 i = 0; i < n; ++i) {
     u64 mask =
         (not_bits && i < not_bits->active_words) ? not_bits->words[i] : 0;
     u64 old = dst->words[i];
     dst->words[i] |= src->words[i] & ~mask;
     changed |= dst->words[i] != old;
+    if (dst->words[i] && active <= i) active = i + 1u;
   }
-  if (changed) opt_bitset_trim(dst);
+  dst->active_words = active;
   return changed;
 }
 
@@ -664,40 +669,29 @@ static void range_live_pregs_update_before(RangeLivePregs* live,
     range_live_pregs_add(live, refs->uses[i]);
 }
 
-static int u32_cmp(const void* a, const void* b) {
-  u32 av = *(const u32*)a;
-  u32 bv = *(const u32*)b;
-  return (av > bv) - (av < bv);
-}
-
-static u32 range_point_index(const u32* points, u32 npoints, u32 raw) {
-  u32 lo = 0;
-  u32 hi = npoints;
-  while (lo < hi) {
-    u32 mid = lo + (hi - lo) / 2u;
-    if (points[mid] < raw)
-      lo = mid + 1u;
-    else
-      hi = mid;
-  }
-  return lo;
-}
-
 static void range_compress_points(OptLiveRangeSet* ranges,
                                   RangeBuildCtx* build) {
   if (build->nraw_points == 0) return;
-  qsort(build->raw_points, build->nraw_points, sizeof(build->raw_points[0]),
-        u32_cmp);
+  u32 raw_count = ranges->raw_point_count;
+  for (u32 i = 0; i < build->nraw_points; ++i)
+    if (build->raw_points[i] >= raw_count) raw_count = build->raw_points[i] + 1u;
+
+  u8* present = arena_zarray(build->f->arena, u8, raw_count ? raw_count : 1u);
+  for (u32 i = 0; i < build->nraw_points; ++i) present[build->raw_points[i]] = 1;
+
+  u32* raw_to_point =
+      arena_array(build->f->arena, u32, raw_count ? raw_count : 1u);
   u32 unique = 0;
-  for (u32 i = 0; i < build->nraw_points; ++i) {
-    if (unique == 0 || build->raw_points[i] != build->raw_points[unique - 1u])
-      build->raw_points[unique++] = build->raw_points[i];
+  for (u32 raw = 0; raw < raw_count; ++raw) {
+    raw_to_point[raw] = unique;
+    if (present[raw]) build->raw_points[unique++] = raw;
   }
   ranges->point_count = unique;
+  ranges->raw_point_count = raw_count;
   for (u32 i = 0; i < ranges->nranges; ++i) {
     OptLiveRange* r = &ranges->ranges[i];
-    r->start = range_point_index(build->raw_points, unique, r->start);
-    r->end = range_point_index(build->raw_points, unique, r->end);
+    r->start = r->start < raw_count ? raw_to_point[r->start] : unique;
+    r->end = r->end < raw_count ? raw_to_point[r->end] : unique;
     if (r->end <= r->start) r->end = r->start + 1u;
     u32 len = r->end - r->start;
     ranges->range_point_visits += len;