Author: Richard Plangger <[email protected]>
Branch: regalloc
Changeset: r78168:0dcfffa6613e
Date: 2015-06-18 11:00 +0200
http://bitbucket.org/pypy/pypy/changeset/0dcfffa6613e/
Log: exchanged the heuristic for the register allocator. it now takes the
live range whose next use is furthest in the future added 2 tests to
check this
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,6 +1,7 @@
import os
from rpython.jit.metainterp.history import Const, Box, REF, JitCellToken
from rpython.rlib.objectmodel import we_are_translated, specialize
+from rpython.rlib.rbisect import bisect_left
from rpython.jit.metainterp.resoperation import rop
from rpython.rtyper.lltypesystem import lltype
from rpython.rtyper.lltypesystem.lloperation import llop
@@ -409,9 +410,12 @@
def _pick_variable_to_spill(self, v, forbidden_vars, selected_reg=None,
need_lower_byte=False):
- """ Slightly less silly algorithm.
+ """ Heuristic: take the variable which has it's next use
+ the furthest in the future.
+ The original heuristic proposed by Poletto & Sarkar takes
+ the live range that ends the last.
"""
- cur_max_age = -1
+ furthest_pos = -1
candidate = None
for next in self.reg_bindings:
reg = self.reg_bindings[next]
@@ -424,9 +428,9 @@
continue
if need_lower_byte and reg in self.no_lower_byte_regs:
continue
- max_age = self.longevity[next][1]
- if cur_max_age < max_age:
- cur_max_age = max_age
+ pos = next_var_usage(self.longevity[next], self.position)
+ if furthest_pos < pos:
+ furthest_pos = pos
candidate = next
if candidate is None:
raise NoVariableToSpill
@@ -673,6 +677,19 @@
else:
return [self.loc(op.getarg(0))]
+def next_var_usage(longevity, pos):
+ start, end, uses = longevity
+ if pos > end:
+ # there is no next usage, has already been passed
+ return -1
+ if pos < start:
+ return start
+ if uses is None:
+ # a live range with just a definition and one use
+ return end
+ i = bisect_left(uses, pos, len(uses))
+ return uses[i]
+
def compute_vars_longevity(inputargs, operations):
# compute a dictionary that maps variables to index in
# operations that is a "last-time-seen"
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
@@ -3,7 +3,7 @@
INT, FLOAT, BoxPtr)
from rpython.jit.metainterp.resoperation import rop, ResOperation
from rpython.jit.backend.llsupport.regalloc import (FrameManager,
- LinkedList, compute_vars_longevity)
+ LinkedList, compute_vars_longevity, next_var_usage)
from rpython.jit.backend.llsupport.regalloc import RegisterManager as
BaseRegMan
def newboxes(*values):
@@ -32,6 +32,13 @@
class RegisterManager(BaseRegMan):
all_regs = regs
+
+ def __init__(self, longevity, frame_manager=None, assembler=None):
+ for k,v in longevity.items():
+ if len(v) == 2:
+ longevity[k] = (v[0], v[1], None)
+ BaseRegMan.__init__(self, longevity, frame_manager, assembler)
+
def convert_to_imm(self, v):
return v
@@ -598,3 +605,40 @@
assert longevity[d] == (4,5, None)
assert longevity[e] == (0,2, None)
assert longevity[f] == (2,5, None)
+
+
+ def test_next_var_usage(self):
+ assert next_var_usage( (0,9,None), 10 ) == -1
+ assert next_var_usage( (4,9,None), 2 ) == 4
+ assert next_var_usage( (0,9,None), -1 ) == 0
+ assert next_var_usage( (0,5,[0,1,2,3,4,5]), 3 ) == 3
+ assert next_var_usage( (1,10,[1,5,8,10]), 4 ) == 5
+ assert next_var_usage( (1,10,[1,5,8,10]), 1 ) == 1
+ assert next_var_usage( (1,10,[1,5,8,10]), 2 ) == 5
+ assert next_var_usage( (1,10,[1,5,8,10]), 9 ) == 10
+
+ def test_pick_to_spill(self):
+ b = [BoxInt() for i in range(0,10)]
+ longevity = {
+ b[0] : (1, 10, [1,2,8,10]),
+ b[1] : (3, 4, None),
+ b[2] : (0, 7, None),
+ }
+ rm = RegisterManager(longevity)
+
+ rm.reg_bindings[b[2]] = None
+ rm.position = 0
+ assert rm._pick_variable_to_spill(None, []) is b[2]
+
+ rm.reg_bindings[b[0]] = None
+ rm.position = 1
+ assert rm._pick_variable_to_spill(None, []) in (b[2],)
+
+ rm.reg_bindings[b[1]] = None
+ rm.position = 3
+ assert rm._pick_variable_to_spill(None, []) in (b[0],)
+
+ del rm.reg_bindings[b[1]]
+ rm.position = 5
+ assert rm._pick_variable_to_spill(None, []) in (b[0],)
+
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
