Author: Carl Friedrich Bolz <[email protected]>
Branch: regalloc-playground
Changeset: r92213:e8eede93629e
Date: 2017-08-22 22:54 +0200
http://bitbucket.org/pypy/pypy/changeset/e8eede93629e/
Log: another heuristic: if there's a fixed register around and the
current to-be-allocated one fits before the next fixed use, use that
(and use the smallest lifetime hole)
diff --git a/rpython/jit/backend/llsupport/regalloc.py
b/rpython/jit/backend/llsupport/regalloc.py
--- a/rpython/jit/backend/llsupport/regalloc.py
+++ b/rpython/jit/backend/llsupport/regalloc.py
@@ -956,6 +956,30 @@
max_free_pos = free_until_pos
return best_reg, max_free_pos
+ def free_reg_whole_lifetime(self, position, v, free_regs):
+ """ try to find a register from free_regs for v at position that's
+ free for the whole lifetime of v. pick the one that is blocked first
+ *after* the lifetime of v. """
+ longevityvar = self[v]
+ min_fixed_use_after = sys.maxint
+ best_reg = None
+ unfixed_reg = None
+ for reg in free_regs:
+ fixed_reg_pos = self.fixed_register_use.get(reg, None)
+ if fixed_reg_pos is None:
+ unfixed_reg = reg
+ continue
+ use_after = fixed_reg_pos.free_until_pos(longevityvar.last_usage)
+ assert use_after >= longevityvar.last_usage
+ if use_after < min_fixed_use_after:
+ best_reg = reg
+ min_fixed_use_after = use_after
+ if best_reg is not None:
+ return best_reg
+
+ # no fitting fixed registers. pick a non-fixed one
+ return unfixed_reg
+
def try_pick_free_reg(self, position, v, free_regs):
if not free_regs:
return None
@@ -965,13 +989,19 @@
if reg is not None and reg in free_regs:
return reg
- # pick the register that's free the longest
+ # try to find a register that's free for the whole lifetime of v
+ # pick the one that is blocked first *after* the lifetime of v
+ loc = self.free_reg_whole_lifetime(position, v, free_regs)
+ if loc is not None:
+ return loc
+
+ # can't fit v completely, so pick the register that's free the longest
loc, free_until = self.longest_free_reg(position, free_regs)
- if loc is None:
- return None
+ if loc is not None:
+ return loc
# YYY could check whether it's best to spill v here, but hard
# to do in the current system
- return loc
+ return None
def __contains__(self, var):
return var in self.longevity
diff --git a/rpython/jit/backend/llsupport/test/test_regalloc.py
b/rpython/jit/backend/llsupport/test/test_regalloc.py
--- a/rpython/jit/backend/llsupport/test/test_regalloc.py
+++ b/rpython/jit/backend/llsupport/test/test_regalloc.py
@@ -52,6 +52,8 @@
return 'r%d' % self.n
r0, r1, r2, r3 = [FakeReg(i) for i in range(4)]
+r4, r5, r6, r7, r8, r9 = [FakeReg(i) for i in range(4, 10)]
+
regs = [r0, r1, r2, r3]
class RegisterManager(BaseRegMan):
@@ -270,6 +272,27 @@
assert longevity.longest_free_reg(0, [r0, r1, r2]) == (r1, 2)
+def test_try_pick_free_reg():
+ b0, b1, b2, b3, b4 = newboxes(0, 0, 0, 0, 0)
+ l0 = Lifetime(0, 4)
+ l1 = Lifetime(2, 20)
+ l2 = Lifetime(6, 20)
+ l3 = Lifetime(8, 20)
+ l4 = Lifetime(0, 10)
+ longevity = LifetimeManager({b0: l0, b1: l1, b2: l2, b3: l3, b4: l4})
+ longevity.fixed_register(3, r1, b1)
+ longevity.fixed_register(7, r2, b2)
+ longevity.fixed_register(9, r3, b3)
+
+ # a best fit
+ loc = longevity.try_pick_free_reg(0, b0, [r1, r2, r3, r4, r5])
+ assert loc is r2
+
+ # does not fit into any of the fixed regs, use a non-fixed one
+ loc = longevity.try_pick_free_reg(0, b4, [r5, r2, r3, r4, r1])
+ assert loc in [r4, r5]
+
+
class TestRegalloc(object):
def test_freeing_vars(self):
b0, b1, b2 = newboxes(0, 0, 0)
@@ -815,7 +838,6 @@
# _____________________________________________________
# tests that assign registers in a mocked way for a fake CPU
-r4, r5, r6, r7, r8, r9 = [FakeReg(i) for i in range(4, 10)]
class RegisterManager2(BaseRegMan):
all_regs = [r0, r1, r2, r3, r4, r5, r6, r7]
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
