Mesa (main): ir3/ra: Use killed sources in register eviction

[GitLab Mirror]

Module: Mesa
Branch: main
Commit: d4b5d2a0204f8c09a2e8c4dc022f0f05adafa50b
URL:    http://cgit.freedesktop.org/mesa/mesa/commit/?id=d4b5d2a0204f8c09a2e8c4dc022f0f05adafa50b

Author: Connor Abbott <cwabbott0 at gmail.com>
Date:   Thu Sep 30 14:52:44 2021 +0200

ir3/ra: Use killed sources in register eviction

Let's assume we have a vec2 collect instruction with killed sources that
are non-contiguous and the entire rest of the register file is blocked,
which can happen when our register target is very tight. It's impossible
to just insert move instructions to resolve this, but we can make space
by swapping one of the killed sources with the value next to the other,
assuming it's also scalar.

This commit implements that idea, preventing us from falling back to the
terrible shuffle-everything approach in this case.

total instructions in shared programs: 1566648 -> 1565117 (-0.10%)
instructions in affected programs: 13332 -> 11801 (-11.48%)
helped: 30
HURT: 5
helped stats (abs) min: 6 max: 535 x̄: 51.77 x̃: 25
helped stats (rel) min: 2.67% max: 33.63% x̄: 12.28% x̃: 9.58%
HURT stats (abs)   min: 1 max: 6 x̄: 4.40 x̃: 6
HURT stats (rel)   min: 0.18% max: 5.13% x̄: 2.41% x̃: 2.13%
95% mean confidence interval for instructions value: -75.05 -12.43
95% mean confidence interval for instructions %-change: -13.18% -7.18%
Instructions are helped.

total mov in shared programs: 77336 -> 76683 (-0.84%)
mov in affected programs: 2135 -> 1482 (-30.59%)
helped: 29
HURT: 5
helped stats (abs) min: 2 max: 227 x̄: 23.31 x̃: 10
helped stats (rel) min: 6.06% max: 72.73% x̄: 31.83% x̃: 30.00%
HURT stats (abs)   min: 2 max: 9 x̄: 4.60 x̃: 4
HURT stats (rel)   min: 14.29% max: 69.23% x̄: 34.00% x̃: 27.78%
95% mean confidence interval for mov value: -33.21 -5.20
95% mean confidence interval for mov %-change: -32.94% -11.35%
Mov are helped.

Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/13143>

---

 src/freedreno/ir3/ir3_ra.c | 65 +++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 64 insertions(+), 1 deletion(-)

diff --git a/src/freedreno/ir3/ir3_ra.c b/src/freedreno/ir3/ir3_ra.c
index 5074dcf3125..656f5c5511f 100644
--- a/src/freedreno/ir3/ir3_ra.c
+++ b/src/freedreno/ir3/ir3_ra.c
@@ -757,8 +757,13 @@ try_evict_regs(struct ra_ctx *ctx, struct ra_file *file,
    memcpy(available_to_evict, file->available_to_evict,
           sizeof(available_to_evict));
 
-   for (unsigned i = 0; i < reg_size(reg); i++)
+   BITSET_DECLARE(available, RA_MAX_FILE_SIZE);
+   memcpy(available, file->available, sizeof(available));
+
+   for (unsigned i = 0; i < reg_size(reg); i++) {
       BITSET_CLEAR(available_to_evict, physreg + i);
+      BITSET_CLEAR(available, physreg + i);
+   }
 
    unsigned eviction_count = 0;
    /* Iterate over each range conflicting with physreg */
@@ -801,6 +806,64 @@ try_evict_regs(struct ra_ctx *ctx, struct ra_file *file,
          }
       }
 
+      if (evicted)
+         continue;
+
+      /* If we couldn't evict this range, we may be able to swap it with a
+       * killed range to acheive the same effect.
+       */
+      foreach_interval (killed, file) {
+         if (!killed->is_killed)
+            continue;
+
+         if (killed->physreg_end - killed->physreg_start !=
+             conflicting->physreg_end - conflicting->physreg_start)
+            continue;
+
+         /* We can't swap the killed range if it partially/fully overlaps the
+          * space we're trying to allocate or (in speculative mode) if it's
+          * already been swapped and will overlap when we actually evict.
+          */
+         bool killed_available = true;
+         for (unsigned i = killed->physreg_start; i < killed->physreg_end; i++) {
+            if (!BITSET_TEST(available, i)) {
+               killed_available = false;
+               break;
+            }
+         }
+         
+         if (!killed_available)
+            continue;
+
+         /* Check for alignment if one is a full reg */
+         if ((!(killed->interval.reg->flags & IR3_REG_HALF) ||
+              !(conflicting->interval.reg->flags & IR3_REG_HALF)) &&
+             (killed->physreg_start % 2 != 0 ||
+              conflicting->physreg_start % 2 != 0))
+            continue;
+
+         for (unsigned i = killed->physreg_start; i < killed->physreg_end; i++) {
+            BITSET_CLEAR(available, i);
+         }
+         /* Because this will generate swaps instead of moves, multiply the
+          * cost by 2.
+          */
+         eviction_count += (killed->physreg_end - killed->physreg_start) * 2;
+         if (!speculative) {
+            physreg_t killed_start = killed->physreg_start,
+                      conflicting_start = conflicting->physreg_start;
+            struct ra_removed_interval killed_removed =
+               ra_pop_interval(ctx, file, killed);
+            struct ra_removed_interval conflicting_removed =
+               ra_pop_interval(ctx, file, conflicting);
+            ra_push_interval(ctx, file, &killed_removed, conflicting_start);
+            ra_push_interval(ctx, file, &conflicting_removed, killed_start);
+         }
+
+         evicted = true;
+         break;
+      }
+
       if (!evicted)
          return false;
    }