Author: Carl Friedrich Bolz <[email protected]>
Branch: regalloc-playground
Changeset: r92201:a961fe5b9c4a
Date: 2017-08-21 20:55 +0200
http://bitbucket.org/pypy/pypy/changeset/a961fe5b9c4a/
Log: implement the most common spilling heuristic used in linear scan
implementations:
spill the variable where the next use as as argument is the furthest
away from the current position.
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
@@ -416,9 +416,13 @@
def _pick_variable_to_spill(self, v, forbidden_vars, selected_reg=None,
need_lower_byte=False):
- """ Slightly less silly algorithm.
- """
- cur_max_age = -1
+ # try to spill a variable that has no further real usages, ie that only
+ # appears in failargs or in a jump
+ # if that doesn't exist, spill the variable that has a real_usage that
+ # is the furthest away from the current position
+
+ cur_max_use_distance = -1
+ position = self.position
candidate = None
cur_max_age_failargs = -1
candidate_from_failargs = None
@@ -434,17 +438,19 @@
if need_lower_byte and reg in self.no_lower_byte_regs:
continue
lifetime = self.longevity[next]
- max_age = lifetime.last_usage
- if lifetime.is_last_real_use_before(self.position):
+ if lifetime.is_last_real_use_before(position):
# this variable has no "real" use as an argument to an op left
# it is only used in failargs, and maybe in a jump. spilling is
# fine
+ max_age = lifetime.last_usage
if cur_max_age_failargs < max_age:
cur_max_age_failargs = max_age
candidate_from_failargs = next
- if cur_max_age < max_age:
- cur_max_age = max_age
- candidate = next
+ else:
+ use_distance = lifetime.next_real_usage(position) - position
+ if cur_max_use_distance < use_distance:
+ cur_max_use_distance = use_distance
+ candidate = next
if candidate_from_failargs is not None:
return candidate_from_failargs
if candidate is not None:
@@ -809,8 +815,7 @@
UNDEF_POS = -42
class Lifetime(object):
- def __init__(self, definition_pos=UNDEF_POS, last_usage=UNDEF_POS,
- last_real_usage=UNDEF_POS):
+ def __init__(self, definition_pos=UNDEF_POS, last_usage=UNDEF_POS):
# all positions are indexes into the operations list
# the position where the variable is defined
@@ -819,16 +824,38 @@
# and jumps
self.last_usage = last_usage
- # last *real* usage, ie as an argument to an operation
- # after last_real_usage and last_usage it does not matter whether the
- # variable is stored on the stack
- self.last_real_usage = last_real_usage
+ # *real* usages, ie as an argument to an operation (as opposed to jump
+ # arguments or in failargs)
+ self.real_usages = None
def is_last_real_use_before(self, position):
- return self.last_real_usage <= position
+ if self.real_usages is None:
+ return True
+ return self.real_usages[-1] <= position
+
+ def next_real_usage(self, position):
+ assert position >= self.definition_pos
+ # binary search
+ l = self.real_usages
+ low = 0
+ high = len(l)
+ while low < high:
+ mid = low + (high - low) // 2 # no overflow ;-)
+ if position < l[mid]:
+ high = mid
+ else:
+ low = mid + 1
+ return l[low]
+
+ def _check_invariants(self):
+ assert self.definition_pos <= self.last_usage
+ if self.real_usages is not None:
+ assert sorted(self.real_usages) == self.real_usages
+ assert self.last_usage >= max(self.real_usages)
+ assert self.definition_pos < min(self.real_usages)
def __repr__(self):
- return "%s:%s(%s)" % (self.definition_pos, self.last_real_usage,
self.last_usage)
+ return "%s:%s(%s)" % (self.definition_pos, self.real_usages,
self.last_usage)
def compute_vars_longevity(inputargs, operations):
# compute a dictionary that maps variables to Lifetime information
@@ -855,8 +882,9 @@
else:
lifetime = longevity[arg]
if opnum != rop.JUMP and opnum != rop.LABEL:
- if lifetime.last_real_usage == UNDEF_POS:
- lifetime.last_real_usage = i
+ if lifetime.real_usages is None:
+ lifetime.real_usages = []
+ lifetime.real_usages.append(i)
if rop.is_guard(op.opnum):
for arg in op.getfailargs():
if arg is None: # hole
@@ -868,7 +896,7 @@
for arg in inputargs:
assert not isinstance(arg, Const)
if arg not in longevity:
- longevity[arg] = Lifetime(-1, -1, -1)
+ longevity[arg] = Lifetime(-1, -1)
if not we_are_translated():
produced = {}
@@ -879,6 +907,11 @@
if not isinstance(arg, Const):
assert arg in produced
produced[op] = None
+ for lifetime in longevity.itervalues():
+ if lifetime.real_usages is not None:
+ lifetime.real_usages.reverse()
+ if not we_are_translated():
+ lifetime._check_invariants()
return 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
@@ -13,10 +13,14 @@
return [InputArgRef() for _ in range(count)]
def Lifetime(definition_pos=UNDEF_POS, last_usage=UNDEF_POS,
- last_real_usage=UNDEF_POS):
- if last_real_usage == UNDEF_POS:
- last_real_usage = last_usage
- return RealLifetime(definition_pos, last_usage, last_real_usage)
+ real_usages=UNDEF_POS):
+ if real_usages == UNDEF_POS:
+ real_usages = last_usage
+ lifetime = RealLifetime(definition_pos, last_usage)
+ if isinstance(real_usages, int):
+ real_usages = [real_usages]
+ lifetime.real_usages = real_usages
+ return lifetime
def boxes_and_longevity(num):
@@ -94,6 +98,16 @@
def regalloc_mov(self, from_loc, to_loc):
self.moves.append((from_loc, to_loc))
+
+def test_lifetime_next_real_usage():
+ lt = RealLifetime(0, 1000)
+ lt.real_usages = [0, 1, 5, 10, 24, 35, 55, 56, 57, 90, 92, 100]
+ for i in range(100):
+ next = lt.next_real_usage(i)
+ assert next in lt.real_usages
+ assert next > i
+ assert lt.real_usages[lt.real_usages.index(next) - 1] <= i
+
class TestRegalloc(object):
def test_freeing_vars(self):
b0, b1, b2 = newboxes(0, 0, 0)
@@ -382,7 +396,7 @@
xrm.loc(f0)
rm.loc(b0)
assert fm.get_frame_depth() == 3
-
+
def test_spilling(self):
b0, b1, b2, b3, b4, b5 = newboxes(0, 1, 2, 3, 4, 5)
longevity = {b0: Lifetime(0, 3), b1: Lifetime(0, 3),
@@ -403,6 +417,27 @@
assert spilled2 is loc
rm._check_invariants()
+ def test_spilling_furthest_next_real_use(self):
+ b0, b1, b2, b3, b4, b5 = newboxes(0, 1, 2, 3, 4, 5)
+ longevity = {b0: Lifetime(0, 3, [1, 2, 3]), b1: Lifetime(0, 3, [3]),
+ b3: Lifetime(0, 4, [1, 2, 3, 4]), b2: Lifetime(0, 2),
+ b4: Lifetime(1, 4), b5: Lifetime(1, 3)}
+ fm = TFrameManager()
+ asm = MockAsm()
+ rm = RegisterManager(longevity, frame_manager=fm, assembler=asm)
+ rm.next_instruction()
+ for b in b0, b1, b2, b3:
+ rm.force_allocate_reg(b)
+ assert len(rm.free_regs) == 0
+ rm.next_instruction()
+ loc = rm.loc(b1)
+ spilled = rm.force_allocate_reg(b4)
+ assert spilled is loc
+ spilled2 = rm.force_allocate_reg(b5)
+ assert spilled2 is loc
+ rm._check_invariants()
+
+
def test_spill_useless_vars_first(self):
b0, b1, b2, b3, b4, b5 = newboxes(0, 1, 2, 3, 4, 5)
longevity = {b0: Lifetime(0, 5), b1: Lifetime(0, 10),
diff --git a/rpython/jit/backend/llsupport/test/test_regalloc_integration.py
b/rpython/jit/backend/llsupport/test/test_regalloc_integration.py
--- a/rpython/jit/backend/llsupport/test/test_regalloc_integration.py
+++ b/rpython/jit/backend/llsupport/test/test_regalloc_integration.py
@@ -409,28 +409,35 @@
def test_longevity(self):
ops = """
- [i0, i1, i2, i3, i4]
- i5 = int_add(i0, i1)
- i6 = int_is_true(i5)
- guard_true(i6) [i0, i4]
- jump(i5, i1, i2, i3, i5)
+ [i0, i1, i2, i3, i4, i10]
+ i5 = int_add(i0, i1) # 0
+ i8 = int_add(i0, i1) # 1 unused result, so not in real_usages
+ i6 = int_is_true(i5) # 2
+ i11 = int_add(i5, i10) # 3
+ guard_true(i6) [i0, i4] # 4
+ jump(i5, i1, i2, i3, i5, i11) # 5
"""
regalloc = self.prepare_loop(ops)
- i0, i1, i2, i3, i4 = self.loop.inputargs
+ i0, i1, i2, i3, i4, i10 = self.loop.inputargs
i5 = self.loop.operations[0]
+ i6 = self.loop.operations[2]
longevity = regalloc.longevity
- longevity[i0].last_usage == 2
- longevity[i0].last_real_usage == 0
- longevity[i1].last_usage == 3
- longevity[i1].last_real_usage == 0
- longevity[i2].last_usage == 3
- longevity[i2].last_real_usage == 0
- longevity[i3].last_usage == 3
- longevity[i3].last_real_usage == 0
- longevity[i4].last_usage == 3
- longevity[i4].last_real_usage == -1
- longevity[i5].last_usage == 3
- longevity[i5].last_real_usage == 2
+ assert longevity[i0].last_usage == 4
+ assert longevity[i0].real_usages == [0]
+ assert longevity[i1].last_usage == 5
+ assert longevity[i1].real_usages == [0]
+ assert longevity[i2].last_usage == 5
+ assert longevity[i2].real_usages is None
+ assert longevity[i3].last_usage == 5
+ assert longevity[i3].real_usages is None
+ assert longevity[i4].last_usage == 4
+ assert longevity[i4].real_usages is None
+ assert longevity[i5].last_usage == 5
+ assert longevity[i5].real_usages == [2, 3]
+ assert longevity[i6].last_usage == 4
+ assert longevity[i6].real_usages == [4]
+ assert longevity[i10].last_usage == 3
+ assert longevity[i10].real_usages == [3]
class TestRegallocCompOps(BaseTestRegalloc):
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
