Author: Carl Friedrich Bolz <[email protected]>
Branch: regalloc-playground
Changeset: r92205:f6baf7f14279
Date: 2017-08-22 15:01 +0200
http://bitbucket.org/pypy/pypy/changeset/f6baf7f14279/
Log: some fundamental data structures for supporting putting boxes into
fixed registers
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
@@ -1,3 +1,4 @@
+import sys
from rpython.jit.metainterp.history import Const, REF, JitCellToken
from rpython.rlib.objectmodel import we_are_translated, specialize
from rpython.jit.metainterp.resoperation import rop, AbstractValue
@@ -827,6 +828,10 @@
# arguments or in failargs)
self.real_usages = None
+ # fixed registers are positions where the variable *needs* to be in a
+ # specific register
+ self.fixed_positions = None
+
def is_last_real_use_before(self, position):
if self.real_usages is None:
return True
@@ -846,6 +851,14 @@
low = mid + 1
return l[low]
+ def fixed_register(self, position, reg):
+ assert self.definition_pos <= position <= self.last_usage
+ if self.fixed_positions is None:
+ self.fixed_positions = []
+ else:
+ assert position > self.fixed_positions[-1][0]
+ self.fixed_positions.append((position, reg))
+
def _check_invariants(self):
assert self.definition_pos <= self.last_usage
if self.real_usages is not None:
@@ -856,12 +869,65 @@
def __repr__(self):
return "%s:%s(%s)" % (self.definition_pos, self.real_usages,
self.last_usage)
+
+class FixedRegisterPositions(object):
+ def __init__(self, register):
+ self.register = register
+
+ self.index_lifetimes = []
+
+ def fixed_register(self, opindex, varlifetime):
+ if self.index_lifetimes:
+ assert opindex > self.index_lifetimes[-1][0]
+ self.index_lifetimes.append((opindex, varlifetime))
+
+ def compute_free_until_pos(self, opindex):
+ for (index, varlifetime) in self.index_lifetimes:
+ if opindex <= index:
+ if varlifetime.definition_pos >= opindex:
+ return varlifetime.definition_pos
+ else:
+ # the variable didn't make it into the register despite
+ # being defined already. so we don't care too much, and can
+ # say that the variable is free until index
+ return index
+ return sys.maxint
+
class LifetimeManager(object):
def __init__(self, longevity):
self.longevity = longevity
- def register_hint(self, opindex, var, register):
- raise NotImplementedError
+ # dictionary maps register to FixedRegisterPositions
+ self.fixed_register_use = {}
+
+ def fixed_register(self, opindex, register, var=None):
+ """ Tell the LifetimeManager that variable var *must* be in register at
+ operation opindex. var can be None, if no variable at all can be in
+ that register at the point."""
+ varlifetime = self.longevity[var]
+ if register not in self.fixed_register_use:
+ self.fixed_register_use[register] =
FixedRegisterPositions(register)
+ self.fixed_register_use[register].fixed_register(opindex, varlifetime)
+ varlifetime.fixed_register(opindex, register)
+
+ def compute_longest_free_reg(self, position, free_regs):
+ """ for every register in free_regs, compute how far into the
+ future that register can remain free, according to the constraints of
+ the fixed registers. Find the register that is free the longest.
Return a tuple
+ (reg, free_until_pos). """
+ free_until_pos = {}
+ max_free_pos = -1
+ best_reg = None
+ for reg in free_regs:
+ fixed_reg_pos = self.fixed_register_use.get(reg, None)
+ if fixed_reg_pos is None:
+ return reg, sys.maxint
+ else:
+ free_until_pos = fixed_reg_pos.compute_free_until_pos(position)
+ if free_until_pos > max_free_pos:
+ best_reg = reg
+ max_free_pos = free_until_pos
+ return best_reg, max_free_pos
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
@@ -1,4 +1,5 @@
import py
+import sys
from rpython.jit.metainterp.history import ConstInt, INT, FLOAT
from rpython.jit.metainterp.history import BasicFailDescr, TargetToken
from rpython.jit.metainterp.resoperation import rop
@@ -7,7 +8,8 @@
from rpython.jit.backend.detect_cpu import getcpuclass
from rpython.jit.backend.llsupport.regalloc import FrameManager, LinkedList
from rpython.jit.backend.llsupport.regalloc import RegisterManager as
BaseRegMan,\
- Lifetime as RealLifetime, UNDEF_POS, BaseRegalloc, compute_vars_longevity
+ Lifetime as RealLifetime, UNDEF_POS, BaseRegalloc,
compute_vars_longevity,\
+ LifetimeManager
from rpython.jit.tool.oparser import parse
from rpython.jit.codewriter.effectinfo import EffectInfo
from rpython.rtyper.lltypesystem import lltype
@@ -123,6 +125,73 @@
assert next > i
assert lt.real_usages[lt.real_usages.index(next) - 1] <= i
+def test_fixed_position():
+ b0, b1, b2 = newboxes(0, 0, 0)
+ l0 = Lifetime(0, 5)
+ l1 = Lifetime(2, 9)
+ l2 = Lifetime(0, 9)
+ longevity = LifetimeManager({b0: l0, b1: l1, b2: l2})
+ longevity.fixed_register(1, r0, b0)
+ longevity.fixed_register(4, r2, b0)
+ longevity.fixed_register(5, r1, b1)
+ longevity.fixed_register(8, r1, b1)
+
+ assert l0.fixed_positions == [(1, r0), (4, r2)]
+ assert l1.fixed_positions == [(5, r1), (8, r1)]
+ assert l2.fixed_positions is None
+
+ fpr0 = longevity.fixed_register_use[r0]
+ fpr1 = longevity.fixed_register_use[r1]
+ fpr2 = longevity.fixed_register_use[r2]
+ assert r3 not in longevity.fixed_register_use
+ assert fpr0.index_lifetimes == [(1, l0)]
+ assert fpr1.index_lifetimes == [(5, l1), (8, l1)]
+ assert fpr2.index_lifetimes == [(4, l0)]
+
+
+def test_compute_free_until_pos():
+ b0, b1, b2 = newboxes(0, 0, 0)
+ l0 = Lifetime(0, 5)
+ l1 = Lifetime(2, 9)
+ l2 = Lifetime(30, 40)
+ longevity = LifetimeManager({b0: l0, b1: l1, b2: l2})
+ longevity.fixed_register(1, r0, b0)
+ longevity.fixed_register(4, r2, b0)
+ longevity.fixed_register(5, r1, b1)
+ longevity.fixed_register(8, r1, b1)
+ longevity.fixed_register(35, r1, b2)
+
+ fpr1 = longevity.fixed_register_use[r1]
+
+ # simple cases: we are before the beginning of the lifetime of the variable
+ # in the fixed register, then it's free until the definition of the
+ # variable
+ assert fpr1.compute_free_until_pos(0) == 2
+ assert fpr1.compute_free_until_pos(1) == 2
+ assert fpr1.compute_free_until_pos(2) == 2
+ assert fpr1.compute_free_until_pos(10) == 30
+ assert fpr1.compute_free_until_pos(20) == 30
+ assert fpr1.compute_free_until_pos(30) == 30
+
+ # after the fixed use, we are fined anyway
+ assert fpr1.compute_free_until_pos(36) == sys.maxint
+ assert fpr1.compute_free_until_pos(50) == sys.maxint
+
+ # asking for a position *after* the definition of the variable in the fixed
+ # register means the variable didn't make it into the fixed register, but
+ # at the latest by the use point it will have to go there
+ assert fpr1.compute_free_until_pos(3) == 5
+ assert fpr1.compute_free_until_pos(4) == 5
+ assert fpr1.compute_free_until_pos(5) == 5
+ assert fpr1.compute_free_until_pos(6) == 8
+ assert fpr1.compute_free_until_pos(7) == 8
+ assert fpr1.compute_free_until_pos(8) == 8
+ assert fpr1.compute_free_until_pos(31) == 35
+ assert fpr1.compute_free_until_pos(32) == 35
+ assert fpr1.compute_free_until_pos(33) == 35
+ assert fpr1.compute_free_until_pos(34) == 35
+ assert fpr1.compute_free_until_pos(35) == 35
+
class TestRegalloc(object):
def test_freeing_vars(self):
b0, b1, b2 = newboxes(0, 0, 0)
@@ -223,7 +292,7 @@
assert isinstance(loc, FakeReg)
assert loc not in [r2, r3]
rm._check_invariants()
-
+
def test_make_sure_var_in_reg(self):
boxes, longevity = boxes_and_longevity(5)
fm = TFrameManager()
@@ -237,7 +306,7 @@
loc = rm.make_sure_var_in_reg(b0)
assert isinstance(loc, FakeReg)
rm._check_invariants()
-
+
def test_force_result_in_reg_1(self):
b0, b1 = newboxes(0, 0)
longevity = {b0: Lifetime(0, 1), b1: Lifetime(1, 3)}
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
