Author: Maciej Fijalkowski <[email protected]>
Branch: jitframe-on-heap
Changeset: r60130:3fe697670da9
Date: 2013-01-17 15:29 +0200
http://bitbucket.org/pypy/pypy/changeset/3fe697670da9/
Log: rework the frame manager to use freelists
diff --git a/pypy/jit/backend/llsupport/regalloc.py
b/pypy/jit/backend/llsupport/regalloc.py
--- a/pypy/jit/backend/llsupport/regalloc.py
+++ b/pypy/jit/backend/llsupport/regalloc.py
@@ -13,16 +13,117 @@
class NoVariableToSpill(Exception):
pass
+class Node(object):
+ def __init__(self, val, next):
+ self.val = val
+ self.next = next
+
+class LinkedList(object):
+ def __init__(self, fm, lst=None):
+ # assume the list is sorted
+ if lst is not None:
+ node = None
+ for item in range(len(lst) - 1, -1, -1):
+ node = Node(fm.get_loc_index(item), node)
+ self.master_node = node
+ else:
+ self.master_node = None
+ self.fm = fm
+
+ def append(self, size, item):
+ key = self.fm.get_loc_index(item)
+ if size == 2:
+ self._append(key)
+ self._append(key + 1)
+ else:
+ assert size == 1
+ self._append(key)
+
+ def _append(self, key):
+ if self.master_node is None or self.master_node.val > key:
+ self.master_node = Node(key, self.master_node)
+ else:
+ node = self.master_node
+ prev_node = self.master_node
+ while node and node.val < key:
+ prev_node = node
+ node = node.next
+ prev_node.next = Node(key, node)
+
+ def pop(self, size, tp):
+ if size == 2:
+ return self._pop_two(tp)
+ assert size == 1
+ if not self.master_node:
+ return None
+ node = self.master_node
+ self.master_node = node.next
+ return self.fm.frame_pos(node.val, tp)
+
+ def _candidate(self, node):
+ return node.val + 1 == node.next.val
+
+ def _pop_two(self, tp):
+ node = self.master_node
+ if node is None or node.next is None:
+ return None
+ if self._candidate(node):
+ self.master_node = node.next.next
+ return self.fm.frame_pos(node.val, tp)
+ prev_node = node
+ node = node.next
+ while True:
+ if node.next is None:
+ return None
+ if self._candidate(node):
+ # pop two
+ prev_node.next = node.next.next
+ return self.fm.frame_pos(node.val, tp)
+ node = node.next
+
+ def __len__(self):
+ """ For tests only
+ """
+ node = self.master_node
+ c = 0
+ while node:
+ node = node.next
+ c += 1
+ return c
+
+ def __repr__(self):
+ if not self.master_node:
+ return 'LinkedList(<empty>)'
+ node = self.master_node
+ l = []
+ while node:
+ l.append(str(node.val))
+ node = node.next
+ return 'LinkedList(%s)' % '->'.join(l)
+
class FrameManager(object):
""" Manage frame positions
+
+ start_free_depth is the start where we can allocate in whatever order
+ we like.
+
+ freelist_gcrefs and freelist_others are free lists of locations that
+ can be used for gcrefs and others. below stack_free_depth. Note
+ that if floats are occupying more than one spot, in order to allocate
+ the correct size, we need to use more than one from the freelist in
+ the consecutive order.
"""
- def __init__(self):
+ def __init__(self, start_free_depth=0, freelist_gcrefs=None,
+ freelist_others=None):
self.bindings = {}
- self.used = [] # list of bools
- self.hint_frame_locations = {}
+ self.current_frame_depth = start_free_depth
+ # we disable hints for now
+ #self.hint_frame_locations = {}
+ self.freelist_gcrefs = LinkedList(self, freelist_gcrefs)
+ self.freelist_others = LinkedList(self, freelist_others)
def get_frame_depth(self):
- return len(self.used)
+ return self.current_frame_depth
def get(self, box):
return self.bindings.get(box, None)
@@ -35,12 +136,12 @@
except KeyError:
pass
# check if we have a hint for this box
- if box in self.hint_frame_locations:
- # if we do, try to reuse the location for this box
- loc = self.hint_frame_locations[box]
- if self.try_to_reuse_location(box, loc):
- return loc
- # no valid hint. make up a new free location
+ #if box in self.hint_frame_locations:
+ # # if we do, try to reuse the location for this box
+ # loc = self.hint_frame_locations[box]
+ # if self.try_to_reuse_location(box, loc):
+ # return loc
+ ## no valid hint. make up a new free location
return self.get_new_loc(box)
def get_new_loc(self, box):
@@ -49,22 +150,26 @@
# that 'size' is a power of two. The reason for doing so is to
# avoid obscure issues in jump.py with stack locations that try
# to move from position (6,7) to position (7,8).
- while self.get_frame_depth() & (size - 1):
- self.used.append(False)
- #
- index = self.get_frame_depth()
- newloc = self.frame_pos(index, box.type)
- for i in range(size):
- self.used.append(True)
- #
- if not we_are_translated(): # extra testing
- testindex = self.get_loc_index(newloc)
- assert testindex == index
- #
+ if box.type == REF:
+ newloc = self.freelist_gcrefs.pop(1, box.type)
+ else:
+ newloc = self.freelist_others.pop(size, box.type)
+
+ if newloc is None:
+ #
+ index = self.get_frame_depth()
+ newloc = self.frame_pos(index, box.type)
+ self.current_frame_depth += size
+ #
+ if not we_are_translated(): # extra testing
+ testindex = self.get_loc_index(newloc)
+ assert testindex == index
+ #
self.bindings[box] = newloc
return newloc
def set_binding(self, box, loc):
+ xxx
self.bindings[box] = loc
#
index = self.get_loc_index(loc)
@@ -77,29 +182,20 @@
self.used[index] = True
index += 1
- def reserve_location_in_frame(self, size):
- frame_depth = self.get_frame_depth()
- for i in range(size):
- self.used.append(True)
- return frame_depth
-
def mark_as_free(self, box):
try:
loc = self.bindings[box]
except KeyError:
return # already gone
del self.bindings[box]
- #
- size = self.frame_size(box.type)
- baseindex = self.get_loc_index(loc)
- if baseindex < 0:
- return
- for i in range(size):
- index = baseindex + i
- assert 0 <= index < len(self.used)
- self.used[index] = False
+ if box.type == REF:
+ self.freelist_gcrefs.append(1, loc)
+ else:
+ size = self.frame_size(box)
+ self.freelist_others.append(size, loc)
def try_to_reuse_location(self, box, loc):
+ xxx
index = self.get_loc_index(loc)
if index < 0:
return False
@@ -125,7 +221,11 @@
@staticmethod
def get_loc_index(loc):
raise NotImplementedError("Purely abstract")
-
+ @staticmethod
+ def newloc(pos, size, tp):
+ """ Reverse of get_loc_index
+ """
+ raise NotImplementedError("Purely abstract")
class RegisterManager(object):
""" Class that keeps track of register allocations
diff --git a/pypy/jit/backend/llsupport/test/test_regalloc.py
b/pypy/jit/backend/llsupport/test/test_regalloc.py
--- a/pypy/jit/backend/llsupport/test/test_regalloc.py
+++ b/pypy/jit/backend/llsupport/test/test_regalloc.py
@@ -1,6 +1,7 @@
import py
-from pypy.jit.metainterp.history import BoxInt, ConstInt, BoxFloat, INT, FLOAT
-from pypy.jit.backend.llsupport.regalloc import FrameManager
+from pypy.jit.metainterp.history import BoxInt, ConstInt, BoxFloat, INT,
FLOAT,\
+ BoxPtr
+from pypy.jit.backend.llsupport.regalloc import FrameManager, LinkedList
from pypy.jit.backend.llsupport.regalloc import RegisterManager as BaseRegMan
from pypy.jit.tool.oparser import parse
from pypy.jit.backend.detect_cpu import getcpuclass
@@ -8,6 +9,9 @@
def newboxes(*values):
return [BoxInt(v) for v in values]
+def newrefboxes(count):
+ return [BoxPtr() for _ in range(count)]
+
def boxes_and_longevity(num):
res = []
longevity = {}
@@ -35,6 +39,21 @@
def __init__(self, pos, box_type):
self.pos = pos
self.box_type = box_type
+ def __repr__(self):
+ return 'FramePos<%d,%s>' % (self.pos, self.box_type)
+ def __eq__(self, other):
+ return self.pos == other.pos and self.box_type == other.box_type
+ def __ne__(self, other):
+ return not self == other
+
+class TFrameManagerEqual(FrameManager):
+ def frame_pos(self, i, box_type):
+ return FakeFramePos(i, box_type)
+ def frame_size(self, box_type):
+ return 1
+ def get_loc_index(self, loc):
+ assert isinstance(loc, FakeFramePos)
+ return loc.pos
class TFrameManager(FrameManager):
def frame_pos(self, i, box_type):
@@ -42,10 +61,8 @@
def frame_size(self, box_type):
if box_type == FLOAT:
return 2
- elif box_type == INT:
+ else:
return 1
- else:
- raise ValueError(box_type)
def get_loc_index(self, loc):
assert isinstance(loc, FakeFramePos)
return loc.pos
@@ -343,9 +360,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: (0, 3), b1: (0, 3), b3: (0, 5), b2: (0, 2), b4: (1,
4), b5: (1, 3)}
@@ -366,6 +381,7 @@
def test_hint_frame_locations_1(self):
+ py.test.skip("xxx")
b0, = newboxes(0)
fm = TFrameManager()
loc123 = FakeFramePos(123, INT)
@@ -376,6 +392,7 @@
assert fm.get_frame_depth() == 124
def test_hint_frame_locations_2(self):
+ py.test.skip("xxx")
b0, b1, b2 = newboxes(0, 1, 2)
longevity = {b0: (0, 1), b1: (0, 2), b2: (0, 2)}
fm = TFrameManager()
@@ -407,6 +424,115 @@
#
rm._check_invariants()
+ def test_linkedlist(self):
+ class Loc(object):
+ def __init__(self, pos, size, tp):
+ self.pos = pos
+ self.size = size
+ self.tp = tp
+
+ class FrameManager(object):
+ @staticmethod
+ def get_loc_index(item):
+ return item.pos
+ @staticmethod
+ def frame_pos(pos, tp):
+ if tp == 13:
+ size = 2
+ else:
+ size = 1
+ return Loc(pos, size, tp)
+
+ fm = FrameManager()
+ l = LinkedList(fm)
+ l.append(1, Loc(1, 1, 0))
+ l.append(1, Loc(4, 1, 0))
+ l.append(1, Loc(2, 1, 0))
+ l.append(1, Loc(0, 1, 0))
+ assert l.master_node.val == 0
+ assert l.master_node.next.val == 1
+ assert l.master_node.next.next.val == 2
+ assert l.master_node.next.next.next.val == 4
+ assert l.master_node.next.next.next.next is None
+ item = l.pop(1, 0)
+ assert item.pos == 0
+ item = l.pop(1, 0)
+ assert item.pos == 1
+ item = l.pop(1, 0)
+ assert item.pos == 2
+ item = l.pop(1, 0)
+ assert item.pos == 4
+ assert l.pop(1, 0) is None
+ l.append(1, Loc(1, 1, 0))
+ l.append(1, Loc(5, 1, 0))
+ l.append(1, Loc(2, 1, 0))
+ l.append(1, Loc(0, 1, 0))
+ item = l.pop(2, 13)
+ assert item.tp == 13
+ assert item.pos == 0
+ assert item.size == 2
+ assert l.pop(2, 0) is None # 2 and 4
+ l.append(1, Loc(4, 1, 0))
+ item = l.pop(2, 13)
+ assert item.pos == 4
+ assert item.size == 2
+ assert l.pop(1, 0).pos == 2
+ assert l.pop(1, 0) is None
+ l.append(2, Loc(1, 2, 0))
+ item = l.pop(2, 13)
+ assert item.pos == 1
+ assert item.tp == 13
+ assert item.size == 2
+
+ def test_frame_manager_basic_equal(self):
+ b0, b1 = newboxes(0, 1)
+ fm = TFrameManagerEqual()
+ loc0 = fm.loc(b0)
+ assert fm.get_loc_index(loc0) == 0
+ #
+ assert fm.get(b1) is None
+ loc1 = fm.loc(b1)
+ assert fm.get_loc_index(loc1) == 1
+ assert fm.get(b1) == loc1
+ #
+ loc0b = fm.loc(b0)
+ assert loc0b == loc0
+ #
+ fm.loc(BoxInt())
+ assert fm.get_frame_depth() == 3
+ #
+ f0 = BoxFloat()
+ locf0 = fm.loc(f0)
+ assert fm.get_loc_index(locf0) == 3
+ assert fm.get_frame_depth() == 4
+ #
+ f1 = BoxFloat()
+ locf1 = fm.loc(f1)
+ assert fm.get_loc_index(locf1) == 4
+ assert fm.get_frame_depth() == 5
+ fm.mark_as_free(b1)
+ assert fm.freelist_others
+ b2 = BoxInt()
+ fm.loc(b2) # should be in the same spot as b1 before
+ assert fm.get(b1) is None
+ assert fm.get(b2) == loc1
+ fm.mark_as_free(b0)
+ p0 = BoxPtr()
+ ploc = fm.loc(p0)
+ assert fm.get_loc_index(ploc) == 5
+ assert fm.get_frame_depth() == 6
+ assert ploc != loc1
+ p1 = BoxPtr()
+ p1loc = fm.loc(p1)
+ assert fm.get_loc_index(p1loc) == 6
+ assert fm.get_frame_depth() == 7
+ fm.mark_as_free(p0)
+ p2 = BoxPtr()
+ p2loc = fm.loc(p2)
+ assert p2loc == ploc
+ assert not fm.freelist_gcrefs
+ assert len(fm.freelist_others) == 1
+
def test_frame_manager_basic(self):
b0, b1 = newboxes(0, 1)
fm = TFrameManager()
@@ -426,60 +552,39 @@
#
f0 = BoxFloat()
locf0 = fm.loc(f0)
- assert fm.get_loc_index(locf0) == 4
- assert fm.get_frame_depth() == 6
+ assert fm.get_loc_index(locf0) == 3
+ assert fm.get_frame_depth() == 5
#
f1 = BoxFloat()
locf1 = fm.loc(f1)
- assert fm.get_loc_index(locf1) == 6
+ assert fm.get_loc_index(locf1) == 5
+ assert fm.get_frame_depth() == 7
+ fm.mark_as_free(b1)
+ assert fm.freelist_others
+ b2 = BoxInt()
+ fm.loc(b2) # should be in the same spot as b1 before
+ assert fm.get(b1) is None
+ assert fm.get(b2) == loc1
+ fm.mark_as_free(b0)
+ p0 = BoxPtr()
+ ploc = fm.loc(p0)
+ assert fm.get_loc_index(ploc) == 7
assert fm.get_frame_depth() == 8
- assert fm.used == [True, True, True, False, True, True, True, True]
- #
- fm.mark_as_free(b0)
- assert fm.used == [False, True, True, False, True, True, True, True]
- fm.mark_as_free(b0)
- assert fm.used == [False, True, True, False, True, True, True, True]
- fm.mark_as_free(f1)
- assert fm.used == [False, True, True, False, True, True, False, False]
- #
- fm.reserve_location_in_frame(1)
+ assert ploc != loc1
+ p1 = BoxPtr()
+ p1loc = fm.loc(p1)
+ assert fm.get_loc_index(p1loc) == 8
assert fm.get_frame_depth() == 9
- assert fm.used == [False, True, True, False, True, True, False, False,
True]
- #
- assert b0 not in fm.bindings
- fm.set_binding(b0, loc0)
- assert b0 in fm.bindings
- assert fm.used == [True, True, True, False, True, True, False, False,
True]
- #
- b3 = BoxInt()
- assert not fm.try_to_reuse_location(b3, loc0)
- assert fm.used == [True, True, True, False, True, True, False, False,
True]
- #
- fm.mark_as_free(b0)
- assert fm.used == [False, True, True, False, True, True, False, False,
True]
- assert fm.try_to_reuse_location(b3, loc0)
- assert fm.used == [True, True, True, False, True, True, False, False,
True]
- #
- fm.mark_as_free(b0) # already free
- assert fm.used == [True, True, True, False, True, True, False, False,
True]
- #
- fm.mark_as_free(b3)
- assert fm.used == [False, True, True, False, True, True, False, False,
True]
+ fm.mark_as_free(p0)
+ p2 = BoxPtr()
+ p2loc = fm.loc(p2)
+ assert p2loc == ploc
+ assert not fm.freelist_gcrefs
+ assert len(fm.freelist_others) == 1
+ fm.mark_as_free(b2)
f3 = BoxFloat()
- assert not fm.try_to_reuse_location(f3, fm.frame_pos(0, FLOAT))
- assert not fm.try_to_reuse_location(f3, fm.frame_pos(1, FLOAT))
- assert not fm.try_to_reuse_location(f3, fm.frame_pos(2, FLOAT))
- assert not fm.try_to_reuse_location(f3, fm.frame_pos(3, FLOAT))
- assert not fm.try_to_reuse_location(f3, fm.frame_pos(4, FLOAT))
- assert not fm.try_to_reuse_location(f3, fm.frame_pos(5, FLOAT))
- assert fm.used == [False, True, True, False, True, True, False, False,
True]
- assert fm.try_to_reuse_location(f3, fm.frame_pos(6, FLOAT))
- assert fm.used == [False, True, True, False, True, True, True, True,
True]
- #
- fm.used = [False]
- assert fm.try_to_reuse_location(BoxFloat(), fm.frame_pos(0, FLOAT))
- assert fm.used == [True, True]
- #
- fm.used = [True]
- assert not fm.try_to_reuse_location(BoxFloat(), fm.frame_pos(0, FLOAT))
- assert fm.used == [True]
+ floc = fm.loc(f3)
+ assert fm.get_loc_index(floc) == 0
+
+ def test_frame_manager_2(self):
+ pass
diff --git a/pypy/jit/backend/x86/assembler.py
b/pypy/jit/backend/x86/assembler.py
--- a/pypy/jit/backend/x86/assembler.py
+++ b/pypy/jit/backend/x86/assembler.py
@@ -2072,6 +2072,7 @@
# like %eax that would be destroyed by this call, *and* they are
# used by arglocs for the *next* call, then trouble; for now we
# will just push/pop them.
+ xxx
from pypy.rpython.memory.gctransform import asmgcroot
css = self._regalloc.close_stack_struct
if css == 0:
diff --git a/pypy/jit/backend/x86/regalloc.py b/pypy/jit/backend/x86/regalloc.py
--- a/pypy/jit/backend/x86/regalloc.py
+++ b/pypy/jit/backend/x86/regalloc.py
@@ -331,6 +331,7 @@
def _update_bindings(self, locs, inputargs):
# XXX this should probably go to llsupport/regalloc.py
+ xxx
used = {}
i = 0
for loc in locs:
@@ -1286,6 +1287,7 @@
# optimization only: fill in the 'hint_frame_locations' dictionary
# of 'fm' based on the JUMP at the end of the loop, by looking
# at where we would like the boxes to be after the jump.
+ return # XXX disabled for now
op = operations[-1]
if op.getopnum() != rop.JUMP:
return
_______________________________________________
pypy-commit mailing list
[email protected]
http://mail.python.org/mailman/listinfo/pypy-commit
