Author: Carl Friedrich Bolz-Tereick <[email protected]>
Branch: regalloc-playground
Changeset: r92218:0c3b2571af1c
Date: 2017-08-23 08:41 +0200
http://bitbucket.org/pypy/pypy/changeset/0c3b2571af1c/
Log: implement chained coalescing. fix a bug in free_reg_whole_lifetime
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
@@ -843,7 +843,7 @@
self.share_with = None
# the other lifetime will have this variable set to self.definition_pos
- self.definition_pos_shared = UNDEF_POS
+ self._definition_pos_shared = UNDEF_POS
def is_last_real_use_before(self, position):
if self.real_usages is None:
@@ -864,6 +864,12 @@
low = mid + 1
return l[low]
+ def definition_pos_shared(self):
+ if self._definition_pos_shared != UNDEF_POS:
+ return self._definition_pos_shared
+ else:
+ return self.definition_pos
+
def fixed_register(self, position, reg):
""" registers a fixed register use for the variable at position in
register reg. returns the position from where on the register should be
@@ -871,10 +877,7 @@
assert self.definition_pos <= position <= self.last_usage
if self.fixed_positions is None:
self.fixed_positions = []
- if self.definition_pos_shared != UNDEF_POS:
- res = self.definition_pos_shared
- else:
- res = self.definition_pos
+ res = self.definition_pos_shared()
else:
assert position > self.fixed_positions[-1][0]
res = self.fixed_positions[-1][0]
@@ -957,7 +960,7 @@
if longevityvar0.last_usage != longevityvar1.definition_pos:
return # not supported for now
longevityvar0.share_with = longevityvar1
- longevityvar1.definition_pos_shared = longevityvar0.definition_pos
+ longevityvar1._definition_pos_shared =
longevityvar0.definition_pos_shared()
def longest_free_reg(self, position, free_regs):
""" for every register in free_regs, compute how far into the future
@@ -993,7 +996,10 @@
if fixed_reg_pos is None:
unfixed_reg = reg
continue
- use_after = fixed_reg_pos.free_until_pos(longevityvar.last_usage)
+ use_after = fixed_reg_pos.free_until_pos(position)
+ if use_after < longevityvar.last_usage:
+ # can't fit
+ continue
assert use_after >= longevityvar.last_usage
if use_after < min_fixed_use_after:
best_reg = reg
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
@@ -297,6 +297,17 @@
loc = longevity.try_pick_free_reg(0, b4, [r1, r2, r3])
assert loc is r3
+def test_try_pick_free_reg_bug():
+ b0, b1, b2, b3, b4 = newboxes(0, 0, 0, 0, 0)
+ l0 = Lifetime(10, 30)
+ l1 = Lifetime(0, 15)
+ longevity = LifetimeManager({b0: l0, b1: l1})
+ longevity.fixed_register(20, r0, b0)
+
+ # does not fit into r0, use r1
+ loc = longevity.try_pick_free_reg(0, b1, [r0, r1])
+ assert loc == r1
+
def test_simple_coalescing():
b0, b1, b2, b3, b4 = newboxes(0, 0, 0, 0, 0)
l0 = Lifetime(0, 4)
@@ -330,6 +341,42 @@
# r1 is picked, because b4 fits before b0
assert loc is r1
+
+def test_chained_coalescing():
+ # 5 + b4
+ # |
+ # 10 + b0 |
+ # | |
+ # | 15 +
+ # |
+ # +
+ # 20
+ # + b1
+ # |
+ # |
+ # |
+ # +
+ # 30
+ # + b2
+ # |
+ # r1 *
+ # |
+ # +
+ # 40
+ b0, b1, b2, b3, b4 = newboxes(0, 0, 0, 0, 0)
+ l0 = Lifetime(10, 20)
+ l1 = Lifetime(20, 30)
+ l2 = Lifetime(30, 40)
+ l4 = Lifetime(5, 15)
+ longevity = LifetimeManager({b0: l0, b1: l1, b2: l2, b4: l4})
+ longevity.try_use_same_register(b0, b1)
+ longevity.try_use_same_register(b1, b2)
+ longevity.fixed_register(35, r1, b2)
+
+ loc = longevity.try_pick_free_reg(5, b4, [r0, r1])
+ assert loc is r0
+
+
class TestRegalloc(object):
def test_freeing_vars(self):
b0, b1, b2 = newboxes(0, 0, 0)
@@ -356,7 +403,7 @@
rm._check_invariants()
assert len(rm.free_regs) == 4
assert len(rm.reg_bindings) == 0
-
+
def test_register_exhaustion(self):
boxes, longevity = boxes_and_longevity(5)
rm = RegisterManager(longevity)
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
