Author: Carl Friedrich Bolz <[email protected]>
Branch: regalloc-playground
Changeset: r92182:32c23f8fb859
Date: 2017-08-18 21:36 +0200
http://bitbucket.org/pypy/pypy/changeset/32c23f8fb859/
Log: a branch to try out some register allocation ideas
first step: refactor lifetime storage to not be tuple-based
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
@@ -293,12 +293,12 @@
def is_still_alive(self, v):
# Check if 'v' is alive at the current position.
# Return False if the last usage is strictly before.
- return self.longevity[v][1] >= self.position
+ return self.longevity[v].last_usage >= self.position
def stays_alive(self, v):
# Check if 'v' stays alive after the current position.
# Return False if the last usage is before or at position.
- return self.longevity[v][1] > self.position
+ return self.longevity[v].last_usage > self.position
def next_instruction(self, incr=1):
self.position += incr
@@ -315,7 +315,7 @@
self._check_type(v)
if isinstance(v, Const):
return
- if v not in self.longevity or self.longevity[v][1] <= self.position:
+ if v not in self.longevity or self.longevity[v].last_usage <=
self.position:
if v in self.reg_bindings:
self.free_regs.append(self.reg_bindings[v])
del self.reg_bindings[v]
@@ -351,7 +351,7 @@
for v in self.reg_bindings:
if v not in self.longevity:
llop.debug_print(lltype.Void, "variable %s not in
longevity\n" % v.repr({}))
- assert self.longevity[v][1] > self.position
+ assert self.longevity[v].last_usage > self.position
def try_allocate_reg(self, v, selected_reg=None, need_lower_byte=False):
""" Try to allocate a register, if we have one free.
@@ -427,7 +427,7 @@
continue
if need_lower_byte and reg in self.no_lower_byte_regs:
continue
- max_age = self.longevity[next][1]
+ max_age = self.longevity[next].last_usage
if cur_max_age < max_age:
cur_max_age = max_age
candidate = next
@@ -446,7 +446,7 @@
"""
self._check_type(v)
if isinstance(v, TempVar):
- self.longevity[v] = (self.position, self.position)
+ self.longevity[v] = Lifetime(self.position, self.position)
loc = self.try_allocate_reg(v, selected_reg,
need_lower_byte=need_lower_byte)
if loc:
@@ -556,7 +556,7 @@
loc = self.force_allocate_reg(v, forbidden_vars)
self.assembler.regalloc_mov(prev_loc, loc)
assert v in self.reg_bindings
- if self.longevity[v][1] > self.position:
+ if self.longevity[v].last_usage > self.position:
# we need to find a new place for variable v and
# store result in the same place
loc = self.reg_bindings[v]
@@ -643,7 +643,7 @@
move_or_spill = []
for v, reg in self.reg_bindings.items():
- max_age = self.longevity[v][1]
+ max_age = self.longevity[v].last_usage
if v not in force_store and max_age <= self.position:
# variable dies
del self.reg_bindings[v]
@@ -765,7 +765,7 @@
# of COND_CALL don't accept a cc as input
if next_op.getarg(0) is not op:
return False
- if self.longevity[op][1] > i + 1:
+ if self.longevity[op].last_usage > i + 1:
return False
if opnum != rop.COND_CALL:
if op in operations[i + 1].getfailargs():
@@ -785,6 +785,10 @@
assert op.numargs() == 1
return [self.loc(op.getarg(0))]
+class Lifetime(object):
+ def __init__(self, definition_pos, last_usage):
+ self.definition_pos = definition_pos
+ self.last_usage = last_usage
def compute_vars_longevity(inputargs, operations):
# compute a dictionary that maps variables to index in
@@ -824,14 +828,14 @@
if arg.type != 'v' and arg in last_used:
assert not isinstance(arg, Const)
assert i < last_used[arg]
- longevity[arg] = (i, last_used[arg])
+ longevity[arg] = Lifetime(i, last_used[arg])
del last_used[arg]
for arg in inputargs:
assert not isinstance(arg, Const)
if arg not in last_used:
- longevity[arg] = (-1, -1)
+ longevity[arg] = Lifetime(-1, -1)
else:
- longevity[arg] = (0, last_used[arg])
+ longevity[arg] = Lifetime(0, last_used[arg])
del last_used[arg]
assert len(last_used) == 0
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,7 +1,7 @@
import py
from rpython.jit.metainterp.history import ConstInt, INT, FLOAT
from rpython.jit.backend.llsupport.regalloc import FrameManager, LinkedList
-from rpython.jit.backend.llsupport.regalloc import RegisterManager as
BaseRegMan
+from rpython.jit.backend.llsupport.regalloc import RegisterManager as
BaseRegMan, Lifetime
from rpython.jit.metainterp.resoperation import InputArgInt, InputArgRef,\
InputArgFloat
@@ -17,7 +17,7 @@
for i in range(num):
box = InputArgInt(0)
res.append(box)
- longevity[box] = (0, 1)
+ longevity[box] = Lifetime(0, 1)
return res, longevity
class FakeReg(object):
@@ -76,7 +76,7 @@
class TestRegalloc(object):
def test_freeing_vars(self):
b0, b1, b2 = newboxes(0, 0, 0)
- longevity = {b0: (0, 1), b1: (0, 2), b2: (0, 2)}
+ longevity = {b0: Lifetime(0, 1), b1: Lifetime(0, 2), b2: Lifetime(0,
2)}
rm = RegisterManager(longevity)
rm.next_instruction()
for b in b0, b1, b2:
@@ -190,7 +190,7 @@
def test_force_result_in_reg_1(self):
b0, b1 = newboxes(0, 0)
- longevity = {b0: (0, 1), b1: (1, 3)}
+ longevity = {b0: Lifetime(0, 1), b1: Lifetime(1, 3)}
fm = TFrameManager()
asm = MockAsm()
rm = RegisterManager(longevity, frame_manager=fm, assembler=asm)
@@ -206,7 +206,7 @@
def test_force_result_in_reg_2(self):
b0, b1 = newboxes(0, 0)
- longevity = {b0: (0, 2), b1: (1, 3)}
+ longevity = {b0: Lifetime(0, 2), b1: Lifetime(1, 3)}
fm = TFrameManager()
asm = MockAsm()
rm = RegisterManager(longevity, frame_manager=fm, assembler=asm)
@@ -222,7 +222,9 @@
def test_force_result_in_reg_3(self):
b0, b1, b2, b3, b4 = newboxes(0, 0, 0, 0, 0)
- longevity = {b0: (0, 2), b1: (0, 2), b3: (0, 2), b2: (0, 2), b4: (1,
3)}
+ longevity = {b0: Lifetime(0, 2), b1: Lifetime(0, 2),
+ b3: Lifetime(0, 2), b2: Lifetime(0, 2),
+ b4: Lifetime(1, 3)}
fm = TFrameManager()
asm = MockAsm()
rm = RegisterManager(longevity, frame_manager=fm, assembler=asm)
@@ -238,7 +240,7 @@
def test_force_result_in_reg_4(self):
b0, b1 = newboxes(0, 0)
- longevity = {b0: (0, 1), b1: (0, 1)}
+ longevity = {b0: Lifetime(0, 1), b1: Lifetime(0, 1)}
fm = TFrameManager()
asm = MockAsm()
rm = RegisterManager(longevity, frame_manager=fm, assembler=asm)
@@ -254,7 +256,7 @@
def test_bogus_make_sure_var_in_reg(self):
b0, = newboxes(0)
- longevity = {b0: (0, 1)}
+ longevity = {b0: Lifetime(0, 1)}
fm = TFrameManager()
asm = MockAsm()
rm = RegisterManager(longevity, frame_manager=fm, assembler=asm)
@@ -350,11 +352,11 @@
fm = TFrameManager()
b0 = InputArgInt()
- longevity = {b0: (0, 1)}
+ longevity = {b0: Lifetime(0, 1)}
asm = MockAsm()
rm = RegisterManager(longevity, frame_manager=fm, assembler=asm)
f0 = InputArgFloat()
- longevity = {f0: (0, 1)}
+ longevity = {f0: Lifetime(0, 1)}
xrm = XRegisterManager(longevity, frame_manager=fm, assembler=asm)
xrm.loc(f0)
rm.loc(b0)
@@ -362,7 +364,9 @@
def test_spilling(self):
b0, b1, b2, b3, b4, b5 = newboxes(0, 1, 2, 3, 4, 5)
- longevity = {b0: (0, 3), b1: (0, 3), b3: (0, 5), b2: (0, 2), b4: (1,
4), b5: (1, 3)}
+ longevity = {b0: Lifetime(0, 3), b1: Lifetime(0, 3),
+ b3: Lifetime(0, 5), b2: Lifetime(0, 2),
+ b4: Lifetime(1, 4), b5: Lifetime(1, 3)}
fm = TFrameManager()
asm = MockAsm()
rm = RegisterManager(longevity, frame_manager=fm, assembler=asm)
@@ -378,7 +382,6 @@
assert spilled2 is loc
rm._check_invariants()
-
def test_hint_frame_locations_1(self):
for hint_value in range(11):
b0, = newboxes(0)
diff --git a/rpython/jit/backend/x86/regalloc.py
b/rpython/jit/backend/x86/regalloc.py
--- a/rpython/jit/backend/x86/regalloc.py
+++ b/rpython/jit/backend/x86/regalloc.py
@@ -511,7 +511,7 @@
# and won't be used after the current operation finishes,
# then swap the role of 'x' and 'y'
if (symm and isinstance(argloc, RegLoc) and
- self.rm.longevity[y][1] == self.rm.position):
+ self.rm.longevity[y].last_usage == self.rm.position):
x, y = y, x
argloc = self.loc(y)
#
diff --git a/rpython/jit/backend/zarch/regalloc.py
b/rpython/jit/backend/zarch/regalloc.py
--- a/rpython/jit/backend/zarch/regalloc.py
+++ b/rpython/jit/backend/zarch/regalloc.py
@@ -1,6 +1,7 @@
from rpython.jit.backend.llsupport.regalloc import (RegisterManager,
FrameManager,
TempVar,
compute_vars_longevity,
- BaseRegalloc,
NoVariableToSpill)
+ BaseRegalloc,
NoVariableToSpill,
+ Lifetime)
from rpython.jit.backend.llsupport.jump import remap_frame_layout_mixed
from rpython.jit.backend.zarch.arch import WORD
from rpython.jit.codewriter import longlong
@@ -255,9 +256,9 @@
self._check_type(even_var)
self._check_type(odd_var)
if isinstance(even_var, TempVar):
- self.longevity[even_var] = (self.position, self.position)
+ self.longevity[even_var] = Lifetime(self.position, self.position)
if isinstance(odd_var, TempVar):
- self.longevity[odd_var] = (self.position, self.position)
+ self.longevity[odd_var] = Lifetime(self.position, self.position)
# this function steps through the following:
# 1) maybe there is an even/odd pair that is always
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
