Author: Armin Rigo <ar...@tunes.org>
Branch:
Changeset: r50308:062e9d06c908
Date: 2011-12-08 16:40 +0100
http://bitbucket.org/pypy/pypy/changeset/062e9d06c908/
Log: Hack: record at least some partial information about which frame
locations are freed, and if a hint is present, try to allocate the
spilled boxes into these free locations. The hints are initialized
based on looking ahead at the final JUMP operation. The goal is to
reduce the number of frame-to-frame MOVs that must be emitted in the
JUMP, by spilling boxes directly to the correct location, when
possible.
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
@@ -23,9 +23,12 @@
return self.frame_bindings.get(box, None)
def loc(self, box):
- res = self.get(box)
- if res is not None:
- return res
+ try:
+ return self.frame_bindings[box]
+ except KeyError:
+ return self.get_new_loc(box)
+
+ def get_new_loc(self, box):
size = self.frame_size(box.type)
self.frame_depth += ((-self.frame_depth) & (size-1))
# ^^^ frame_depth is rounded up to a multiple of 'size', assuming
@@ -67,8 +70,17 @@
self.position = -1
self.frame_manager = frame_manager
self.assembler = assembler
+ self.hint_frame_locations = {} # {Box: StackLoc}
+ self.freed_frame_locations = {} # {StackLoc: None}
+
+ 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
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
def next_instruction(self, incr=1):
@@ -84,11 +96,16 @@
point for all variables that might be in registers.
"""
self._check_type(v)
- if isinstance(v, Const) or v not in self.reg_bindings:
+ if isinstance(v, Const):
return
if v not in self.longevity or self.longevity[v][1] <= self.position:
- self.free_regs.append(self.reg_bindings[v])
- del self.reg_bindings[v]
+ if v in self.reg_bindings:
+ self.free_regs.append(self.reg_bindings[v])
+ del self.reg_bindings[v]
+ if self.frame_manager is not None:
+ if v in self.frame_manager.frame_bindings:
+ loc = self.frame_manager.frame_bindings[v]
+ self.freed_frame_locations[loc] = None
def possibly_free_vars(self, vars):
""" Same as 'possibly_free_var', but for all v in vars.
@@ -160,6 +177,23 @@
self.reg_bindings[v] = loc
return loc
+ def _frame_loc(self, v):
+ # first check if it's already in the frame_manager
+ try:
+ return self.frame_manager.frame_bindings[v]
+ except KeyError:
+ pass
+ # check if we have a hint for this box
+ if v in self.hint_frame_locations:
+ # if we do, check that the hinted location is known to be free
+ loc = self.hint_frame_locations[v]
+ if loc in self.freed_frame_locations:
+ del self.freed_frame_locations[loc]
+ self.frame_manager.frame_bindings[v] = loc
+ return loc
+ # no valid hint. make up a new free location
+ return self.frame_manager.get_new_loc(v)
+
def _spill_var(self, v, forbidden_vars, selected_reg,
need_lower_byte=False):
v_to_spill = self._pick_variable_to_spill(v, forbidden_vars,
@@ -167,7 +201,7 @@
loc = self.reg_bindings[v_to_spill]
del self.reg_bindings[v_to_spill]
if self.frame_manager.get(v_to_spill) is None:
- newloc = self.frame_manager.loc(v_to_spill)
+ newloc = self._frame_loc(v_to_spill)
self.assembler.regalloc_mov(loc, newloc)
return loc
@@ -244,7 +278,7 @@
except KeyError:
if box in self.bindings_to_frame_reg:
return self.frame_reg
- return self.frame_manager.loc(box)
+ return self._frame_loc(box)
def return_constant(self, v, forbidden_vars=[], selected_reg=None):
""" Return the location of the constant v. If 'selected_reg' is
@@ -292,7 +326,7 @@
self.reg_bindings[v] = loc
self.assembler.regalloc_mov(prev_loc, loc)
else:
- loc = self.frame_manager.loc(v)
+ loc = self._frame_loc(v)
self.assembler.regalloc_mov(prev_loc, loc)
def force_result_in_reg(self, result_v, v, forbidden_vars=[]):
@@ -311,7 +345,7 @@
self.reg_bindings[result_v] = loc
return loc
if v not in self.reg_bindings:
- prev_loc = self.frame_manager.loc(v)
+ prev_loc = self._frame_loc(v)
loc = self.force_allocate_reg(v, forbidden_vars)
self.assembler.regalloc_mov(prev_loc, loc)
assert v in self.reg_bindings
@@ -331,7 +365,7 @@
def _sync_var(self, v):
if not self.frame_manager.get(v):
reg = self.reg_bindings[v]
- to = self.frame_manager.loc(v)
+ to = self._frame_loc(v)
self.assembler.regalloc_mov(reg, to)
# otherwise it's clean
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
@@ -348,3 +348,50 @@
spilled2 = rm.force_allocate_reg(b5)
assert spilled2 is loc
rm._check_invariants()
+
+
+ def test_hint_frame_locations_1(self):
+ b0, b1 = newboxes(0, 1)
+ longevity = {b0: (0, 1), b1: (0, 1)}
+ fm = TFrameManager()
+ asm = MockAsm()
+ rm = RegisterManager(longevity, frame_manager=fm, assembler=asm)
+ rm.hint_frame_locations[b0] = "some_stack_loc"
+ rm.freed_frame_locations["some_stack_loc"] = None
+ rm.force_allocate_reg(b0)
+ rm.force_allocate_reg(b1)
+ rm.force_spill_var(b0)
+ rm.force_spill_var(b1)
+ assert rm.loc(b0) == "some_stack_loc"
+ assert isinstance(rm.loc(b1), FakeFramePos)
+ rm._check_invariants()
+
+ def test_hint_frame_locations_2(self):
+ b0, b1, b2 = newboxes(0, 1, 2)
+ longevity = {b0: (0, 1), b1: (0, 2), b2: (0, 2)}
+ fm = TFrameManager()
+ asm = MockAsm()
+ rm = RegisterManager(longevity, frame_manager=fm, assembler=asm)
+ rm.force_allocate_reg(b0)
+ rm.force_allocate_reg(b1)
+ rm.force_allocate_reg(b2)
+ rm.force_spill_var(b0)
+ loc = rm.loc(b0)
+ assert isinstance(loc, FakeFramePos)
+ rm.position = 1
+ assert loc not in rm.freed_frame_locations
+ rm.possibly_free_var(b0)
+ assert loc in rm.freed_frame_locations
+ #
+ rm.hint_frame_locations[b1] = loc
+ rm.force_spill_var(b1)
+ loc1 = rm.loc(b1)
+ assert loc1 is loc
+ assert rm.freed_frame_locations == {}
+ #
+ rm.hint_frame_locations[b2] = loc
+ rm.force_spill_var(b2)
+ loc2 = rm.loc(b2)
+ assert loc2 is not loc1 # because it's not in freed_frame_locations
+ #
+ rm._check_invariants()
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
@@ -690,6 +690,7 @@
def _assemble(self, regalloc, operations):
self._regalloc = regalloc
+ regalloc.compute_hint_frame_locations(operations)
regalloc.walk_operations(operations)
if we_are_translated() or self.cpu.dont_keepalive_stuff:
self._regalloc = None # else keep it around for debugging
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
@@ -1318,6 +1318,29 @@
self.rm.possibly_free_var(tmpbox_low)
self.rm.possibly_free_var(tmpbox_high)
+ def compute_hint_frame_locations(self, operations):
+ # optimization only: fill in the 'hint_frame_locations' dictionary
+ # of rm and xrm based on the JUMP at the end of the loop, by looking
+ # at where we would like the boxes to be after the jump.
+ op = operations[-1]
+ if op.getopnum() != rop.JUMP:
+ return
+ descr = op.getdescr()
+ assert isinstance(descr, LoopToken)
+ nonfloatlocs, floatlocs = self.assembler.target_arglocs(descr)
+ for i in range(op.numargs()):
+ box = op.getarg(i)
+ if isinstance(box, Box):
+ loc = nonfloatlocs[i]
+ if isinstance(loc, StackLoc):
+ assert box.type != FLOAT
+ self.rm.hint_frame_locations[box] = loc
+ else:
+ loc = floatlocs[i]
+ if isinstance(loc, StackLoc):
+ assert box.type == FLOAT
+ self.xrm.hint_frame_locations[box] = loc
+
def consider_jump(self, op):
assembler = self.assembler
assert self.jump_target_descr is None
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit
