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 from rpython.jit.metainterp.resoperation import InputArgInt, InputArgRef,\ InputArgFloat 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,\ LifetimeManager from rpython.jit.tool.oparser import parse from rpython.jit.codewriter.effectinfo import EffectInfo from rpython.rtyper.lltypesystem import lltype from rpython.rtyper.annlowlevel import llhelper def newboxes(*values): return [InputArgInt(v) for v in values] def newrefboxes(count): return [InputArgRef() for _ in range(count)] def Lifetime(definition_pos=UNDEF_POS, last_usage=UNDEF_POS, real_usages=UNDEF_POS): if real_usages == UNDEF_POS: real_usages = last_usage lifetime = RealLifetime(definition_pos, last_usage) if isinstance(real_usages, int): real_usages = [real_usages] lifetime.real_usages = real_usages return lifetime def boxes_and_longevity(num): res = [] longevity = {} for i in range(num): box = InputArgInt(0) res.append(box) longevity[box] = Lifetime(0, 1) return res, longevity class FakeReg(object): def __init__(self, i): self.n = i def _getregkey(self): return self.n def is_memory_reference(self): return False def __repr__(self): return 'r%d' % self.n r0, r1, r2, r3 = [FakeReg(i) for i in range(4)] r4, r5, r6, r7, r8, r9 = [FakeReg(i) for i in range(4, 10)] regs = [r0, r1, r2, r3] class RegisterManager(BaseRegMan): all_regs = regs def __init__(self, longevity, frame_manager=None, assembler=None): if isinstance(longevity, dict): longevity = LifetimeManager(longevity) BaseRegMan.__init__(self, longevity, frame_manager, assembler) def convert_to_imm(self, v): return v class FakeFramePos(object): def __init__(self, pos, box_type): self.pos = pos self.value = pos self.box_type = box_type def _getregkey(self): return ~self.value def is_memory_reference(self): return True 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): return FakeFramePos(i, box_type) def frame_size(self, box_type): if box_type == FLOAT: return 2 else: return 1 def get_loc_index(self, loc): assert isinstance(loc, FakeFramePos) return loc.pos class FakeCPU(object): def get_baseofs_of_frame_field(self): return 0 class MockAsm(object): def __init__(self): self.moves = [] self.emitted = [] self.cpu = FakeCPU() # XXX register allocation statistics to be removed later self.num_moves_calls = 0 self.num_moves_jump = 0 self.num_spills = 0 self.num_spills_to_existing = 0 self.num_reloads = 0 self.preamble_num_moves_calls = 0 self.preamble_num_moves_jump = 0 self.preamble_num_spills = 0 self.preamble_num_spills_to_existing = 0 self.preamble_num_reloads = 0 def regalloc_mov(self, from_loc, to_loc): self.moves.append((from_loc, to_loc)) self.emitted.append(("move", to_loc, from_loc)) def test_lifetime_next_real_usage(): lt = RealLifetime(0, 1000) lt.real_usages = [0, 1, 5, 10, 24, 35, 55, 56, 57, 90, 92, 100] for i in range(100): next = lt.next_real_usage(i) assert next in lt.real_usages assert next > i assert lt.real_usages[lt.real_usages.index(next) - 1] <= i assert lt.next_real_usage(100) == -1 assert lt.next_real_usage(101) == -1 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, 0)] assert fpr1.index_lifetimes == [(5, 2), (8, 5)] assert fpr2.index_lifetimes == [(4, 1)] def test_fixed_position_none(): 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) longevity.fixed_register(4, r2) longevity.fixed_register(5, r1) longevity.fixed_register(8, r1) 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, 1)] assert fpr1.index_lifetimes == [(5, 5), (8, 8)] assert fpr2.index_lifetimes == [(4, 4)] def test_free_until_pos_none(): longevity = LifetimeManager({}) longevity.fixed_register(5, r1, None) longevity.fixed_register(8, r1, None) longevity.fixed_register(35, r1, None) fpr1 = longevity.fixed_register_use[r1] assert fpr1.free_until_pos(0) == 5 assert fpr1.free_until_pos(1) == 5 assert fpr1.free_until_pos(2) == 5 assert fpr1.free_until_pos(3) == 5 assert fpr1.free_until_pos(4) == 5 assert fpr1.free_until_pos(5) == 5 assert fpr1.free_until_pos(10) == 35 assert fpr1.free_until_pos(20) == 35 assert fpr1.free_until_pos(30) == 35 assert fpr1.free_until_pos(36) == sys.maxint def test_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(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.free_until_pos(0) == 2 assert fpr1.free_until_pos(1) == 2 assert fpr1.free_until_pos(2) == 2 assert fpr1.free_until_pos(10) == 30 assert fpr1.free_until_pos(20) == 30 assert fpr1.free_until_pos(30) == 30 # after the fixed use, we are fine anyway assert fpr1.free_until_pos(36) == sys.maxint assert fpr1.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.free_until_pos(3) == 5 assert fpr1.free_until_pos(4) == 5 assert fpr1.free_until_pos(5) == 5 assert fpr1.free_until_pos(6) == 8 assert fpr1.free_until_pos(7) == 8 assert fpr1.free_until_pos(8) == 8 assert fpr1.free_until_pos(31) == 35 assert fpr1.free_until_pos(32) == 35 assert fpr1.free_until_pos(33) == 35 assert fpr1.free_until_pos(34) == 35 assert fpr1.free_until_pos(35) == 35 def test_free_until_pos_different_regs(): 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) fpr2 = longevity.fixed_register_use[r2] # the definition of b0 is before the other fixed register use of r0, so the # earliest b0 can be in r2 is that use point at index 1 assert fpr2.free_until_pos(0) == 1 def test_longest_free_reg(): 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) assert longevity.longest_free_reg(0, [r0, r1, r2]) == (r1, 2) def test_try_pick_free_reg(): b0, b1, b2, b3, b4 = newboxes(0, 0, 0, 0, 0) l0 = Lifetime(0, 4) l1 = Lifetime(2, 20) l2 = Lifetime(6, 20) l3 = Lifetime(8, 20) l4 = Lifetime(0, 10) longevity = LifetimeManager({b0: l0, b1: l1, b2: l2, b3: l3, b4: l4}) longevity.fixed_register(3, r1, b1) longevity.fixed_register(7, r2, b2) longevity.fixed_register(9, r3, b3) # a best fit loc = longevity.try_pick_free_reg(0, b0, [r1, r2, r3, r4, r5]) assert loc is r2 # does not fit into any of the fixed regs, use a non-fixed one loc = longevity.try_pick_free_reg(0, b4, [r5, r2, r3, r4, r1]) assert loc in [r4, r5] # all available are fixed but var doesn't fit completely into any of these. # pick the biggest interval loc = longevity.try_pick_free_reg(0, b4, [r1, r2, r3]) assert loc is r3 def test_try_pick_free_reg_bug(): b0, b1, b2, b3, b4 = newboxes(0, 0, 0, 0, 0) l0 = Lifetime(10, 30) l1 = Lifetime(0, 15) longevity = LifetimeManager({b0: l0, b1: l1}) longevity.fixed_register(20, r0, b0) # does not fit into r0, use r1 loc = longevity.try_pick_free_reg(0, b1, [r0, r1]) assert loc == r1 def test_try_pick_free_reg_bug2(): b0, b1, b2, b3, b4 = newboxes(0, 0, 0, 0, 0) l0 = Lifetime(1, 2) l1 = Lifetime(2, 4) longevity = LifetimeManager({b0: l0, b1: l1}) longevity.fixed_register(4, r1, b1) # does not fit into r0, use r1 loc = longevity.try_pick_free_reg(0, b0, [r0, r1]) assert loc == r0 def test_simple_coalescing(): b0, b1, b2, b3, b4 = newboxes(0, 0, 0, 0, 0) l0 = Lifetime(0, 4) l1 = Lifetime(4, 20) l2 = Lifetime(4, 20) longevity = LifetimeManager({b0: l0, b1: l1, b2: l2}) longevity.fixed_register(10, r1, b1) longevity.fixed_register(10, r2, b2) longevity.try_use_same_register(b0, b2) loc = longevity.try_pick_free_reg(0, b0, [r0, r1, r2, r3, r4]) assert loc is r2 def test_coalescing_blocks_regs_correctly(): b0, b1, b2, b3, b4 = newboxes(0, 0, 0, 0, 0) l0 = Lifetime(10, 30) l1 = Lifetime(30, 40) l2 = Lifetime(30, 40) l3 = Lifetime(0, 15) l4 = Lifetime(0, 5) longevity = LifetimeManager({b0: l0, b1: l1, b2: l2, b3: l3, b4: l4}) longevity.try_use_same_register(b0, b1) longevity.fixed_register(35, r1, b1) longevity.fixed_register(35, r2, b2) loc = longevity.try_pick_free_reg(0, b3, [r1, r2]) # r2 is picked, otherwise b0 can't end up in r1 assert loc is r2 loc = longevity.try_pick_free_reg(0, b4, [r1, r2]) # r1 is picked, because b4 fits before b0 assert loc is r1 def test_coalescing_non_fixed_regs(): b0, b1, b2, b3, b4 = newboxes(0, 0, 0, 0, 0) l0 = Lifetime(0, 10) l1 = Lifetime(10, 20) l2 = Lifetime(25, 40) l3 = Lifetime(15, 40) longevity = LifetimeManager({b0: l0, b1: l1, b2: l2, b3: l3}) longevity.try_use_same_register(b0, b1) longevity.fixed_register(35, r2, b2) longevity.fixed_register(35, r3, b3) loc = longevity.try_pick_free_reg(0, b0, [r1, r2, r3]) # r2 is picked, otherwise b1 can't end up in the same reg as b0 assert loc is r2 def test_chained_coalescing(): # 5 + b4 # | # 10 + b0 | # | | # | 15 + # | # + # 20 # + b1 # | # | # | # + # 30 # + b2 # | # r1 * # | # + # 40 b0, b1, b2, b3, b4 = newboxes(0, 0, 0, 0, 0) l0 = Lifetime(10, 20) l1 = Lifetime(20, 30) l2 = Lifetime(30, 40) l4 = Lifetime(5, 15) longevity = LifetimeManager({b0: l0, b1: l1, b2: l2, b4: l4}) longevity.try_use_same_register(b0, b1) longevity.try_use_same_register(b1, b2) longevity.fixed_register(35, r1, b2) loc = longevity.try_pick_free_reg(5, b4, [r0, r1]) assert loc is r0 class TestRegalloc(object): def test_freeing_vars(self): b0, b1, b2 = newboxes(0, 0, 0) 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: rm.try_allocate_reg(b) rm._check_invariants() assert len(rm.free_regs) == 1 assert len(rm.reg_bindings) == 3 rm.possibly_free_vars([b0, b1, b2]) assert len(rm.free_regs) == 1 assert len(rm.reg_bindings) == 3 rm._check_invariants() rm.next_instruction() rm.possibly_free_vars([b0, b1, b2]) rm._check_invariants() assert len(rm.free_regs) == 2 assert len(rm.reg_bindings) == 2 rm._check_invariants() rm.next_instruction() rm.possibly_free_vars([b0, b1, b2]) rm._check_invariants() assert len(rm.free_regs) == 4 assert len(rm.reg_bindings) == 0 def test_register_exhaustion(self): boxes, longevity = boxes_and_longevity(5) rm = RegisterManager(longevity) rm.next_instruction() for b in boxes[:len(regs)]: assert rm.try_allocate_reg(b) assert rm.try_allocate_reg(boxes[-1]) is None rm._check_invariants() def test_need_lower_byte(self): boxes, longevity = boxes_and_longevity(5) b0, b1, b2, b3, b4 = boxes class XRegisterManager(RegisterManager): no_lower_byte_regs = [r2, r3] rm = XRegisterManager(longevity) rm.next_instruction() loc0 = rm.try_allocate_reg(b0, need_lower_byte=True) assert loc0 not in XRegisterManager.no_lower_byte_regs loc = rm.try_allocate_reg(b1, need_lower_byte=True) assert loc not in XRegisterManager.no_lower_byte_regs loc = rm.try_allocate_reg(b2, need_lower_byte=True) assert loc is None loc = rm.try_allocate_reg(b0, need_lower_byte=True) assert loc is loc0 rm._check_invariants() def test_specific_register(self): boxes, longevity = boxes_and_longevity(5) rm = RegisterManager(longevity) rm.next_instruction() loc = rm.try_allocate_reg(boxes[0], selected_reg=r1) assert loc is r1 loc = rm.try_allocate_reg(boxes[1], selected_reg=r1) assert loc is None rm._check_invariants() loc = rm.try_allocate_reg(boxes[0], selected_reg=r1) assert loc is r1 loc = rm.try_allocate_reg(boxes[0], selected_reg=r2) assert loc is r2 rm._check_invariants() def test_force_allocate_reg(self): boxes, longevity = boxes_and_longevity(5) b0, b1, b2, b3, b4 = boxes fm = TFrameManager() class XRegisterManager(RegisterManager): no_lower_byte_regs = [r2, r3] rm = XRegisterManager(longevity, frame_manager=fm, assembler=MockAsm()) rm.next_instruction() loc = rm.force_allocate_reg(b0) assert isinstance(loc, FakeReg) loc = rm.force_allocate_reg(b1) assert isinstance(loc, FakeReg) loc = rm.force_allocate_reg(b2) assert isinstance(loc, FakeReg) loc = rm.force_allocate_reg(b3) assert isinstance(loc, FakeReg) loc = rm.force_allocate_reg(b4) assert isinstance(loc, FakeReg) # one of those should be now somewhere else locs = [rm.loc(b) for b in boxes] used_regs = [loc for loc in locs if isinstance(loc, FakeReg)] assert len(used_regs) == len(regs) loc = rm.force_allocate_reg(b0, need_lower_byte=True) 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() rm = RegisterManager(longevity, frame_manager=fm, assembler=MockAsm()) rm.next_instruction() # allocate a stack position b0, b1, b2, b3, b4 = boxes sp = fm.loc(b0) assert sp.pos == 0 loc = rm.make_sure_var_in_reg(b0) assert isinstance(loc, FakeReg) rm._check_invariants() def test_bogus_make_sure_var_in_reg(self): b0, = newboxes(0) longevity = {b0: Lifetime(0, 1)} fm = TFrameManager() asm = MockAsm() rm = RegisterManager(longevity, frame_manager=fm, assembler=asm) rm.next_instruction() # invalid call to make_sure_var_in_reg(): box unknown so far py.test.raises(KeyError, rm.make_sure_var_in_reg, b0) def test_return_constant(self): asm = MockAsm() boxes, longevity = boxes_and_longevity(5) fm = TFrameManager() rm = RegisterManager(longevity, assembler=asm, frame_manager=fm) rm.next_instruction() loc = rm.return_constant(ConstInt(1), selected_reg=r1) assert loc is r1 loc = rm.return_constant(ConstInt(1), selected_reg=r1) assert loc is r1 loc = rm.return_constant(ConstInt(1)) assert isinstance(loc, ConstInt) for box in boxes[:-1]: rm.force_allocate_reg(box) assert len(asm.moves) == 2 # Const(1) -> r1, twice assert len(rm.reg_bindings) == 4 rm._check_invariants() def test_loc_of_const(self): rm = RegisterManager({}) rm.next_instruction() assert isinstance(rm.loc(ConstInt(1)), ConstInt) def test_call_support(self): class XRegisterManager(RegisterManager): save_around_call_regs = [r1, r2] def call_result_location(self, v): return r1 fm = TFrameManager() asm = MockAsm() boxes, longevity = boxes_and_longevity(5) rm = XRegisterManager(longevity, frame_manager=fm, assembler=asm) for b in boxes[:-1]: rm.force_allocate_reg(b) rm.position = 0 rm.before_call() assert len(rm.reg_bindings) == 2 assert fm.get_frame_depth() == 2 assert len(asm.moves) == 2 rm._check_invariants() rm.after_call(boxes[-1]) assert len(rm.reg_bindings) == 3 rm._check_invariants() def test_call_support_save_all_regs(self): class XRegisterManager(RegisterManager): save_around_call_regs = [r1, r2] def call_result_location(self, v): return r1 fm = TFrameManager() asm = MockAsm() boxes, longevity = boxes_and_longevity(5) rm = XRegisterManager(longevity, frame_manager=fm, assembler=asm) for b in boxes[:-1]: rm.force_allocate_reg(b) rm.before_call(save_all_regs=True) assert len(rm.reg_bindings) == 0 assert fm.get_frame_depth() == 4 assert len(asm.moves) == 4 rm._check_invariants() rm.after_call(boxes[-1]) assert len(rm.reg_bindings) == 1 rm._check_invariants() def test_different_frame_width(self): class XRegisterManager(RegisterManager): pass fm = TFrameManager() b0 = InputArgInt() longevity = {b0: Lifetime(0, 1)} asm = MockAsm() rm = RegisterManager(longevity, frame_manager=fm, assembler=asm) f0 = InputArgFloat() longevity = {f0: Lifetime(0, 1)} xrm = XRegisterManager(longevity, frame_manager=fm, assembler=asm) 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: 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) rm.next_instruction() for b in b0, b1, b2, b3: rm.force_allocate_reg(b) assert len(rm.free_regs) == 0 rm.next_instruction() loc = rm.loc(b3) spilled = rm.force_allocate_reg(b4) assert spilled is loc spilled2 = rm.force_allocate_reg(b5) assert spilled2 is loc rm._check_invariants() def test_spilling_furthest_next_real_use(self): b0, b1, b2, b3, b4, b5 = newboxes(0, 1, 2, 3, 4, 5) longevity = {b0: Lifetime(0, 3, [1, 2, 3]), b1: Lifetime(0, 3, [3]), b3: Lifetime(0, 4, [1, 2, 3, 4]), b2: Lifetime(0, 2), b4: Lifetime(1, 4), b5: Lifetime(1, 3)} fm = TFrameManager() asm = MockAsm() rm = RegisterManager(longevity, frame_manager=fm, assembler=asm) rm.next_instruction() for b in b0, b1, b2, b3: rm.force_allocate_reg(b) assert len(rm.free_regs) == 0 rm.next_instruction() loc = rm.loc(b1) spilled = rm.force_allocate_reg(b4) assert spilled is loc spilled2 = rm.force_allocate_reg(b5) assert spilled2 is loc rm._check_invariants() def test_spill_useless_vars_first(self): b0, b1, b2, b3, b4, b5 = newboxes(0, 1, 2, 3, 4, 5) longevity = {b0: Lifetime(0, 5), b1: Lifetime(0, 10), # b2 and b3 become useless but b3 lives longer b3: Lifetime(0, 7, 3), b2: Lifetime(0, 6, 3), b4: Lifetime(4, 5), b5: Lifetime(4, 7)} fm = TFrameManager() asm = MockAsm() rm = RegisterManager(longevity, frame_manager=fm, assembler=asm) rm.next_instruction() for b in b0, b1, b2, b3: rm.force_allocate_reg(b) rm.position = 4 assert len(rm.free_regs) == 0 loc = rm.loc(b3) spilled = rm.force_allocate_reg(b4) assert spilled is loc loc = rm.loc(b2) spilled2 = rm.force_allocate_reg(b5) assert spilled2 is loc rm._check_invariants() def test_hint_frame_locations_1(self): for hint_value in range(11): b0, = newboxes(0) fm = TFrameManager() fm.hint_frame_pos[b0] = hint_value blist = newboxes(*range(10)) for b1 in blist: fm.loc(b1) for b1 in blist: fm.mark_as_free(b1) assert fm.get_frame_depth() == 10 loc = fm.loc(b0) if hint_value < 10: expected = hint_value else: expected = 0 assert fm.get_loc_index(loc) == expected assert fm.get_frame_depth() == 10 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)) # this will not work because the result will be odd assert l.pop(2, 13) is None l.append(1, Loc(3, 1, 0)) item = l.pop(2, 13) assert item.pos == 2 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(InputArgInt()) assert fm.get_frame_depth() == 3 # f0 = InputArgFloat() locf0 = fm.loc(f0) assert fm.get_loc_index(locf0) == 3 assert fm.get_frame_depth() == 4 # f1 = InputArgFloat() 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 b2 = InputArgInt() 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 = InputArgRef() ploc = fm.loc(p0) assert fm.get_loc_index(ploc) == 0 assert fm.get_frame_depth() == 5 assert ploc != loc1 p1 = InputArgRef() p1loc = fm.loc(p1) assert fm.get_loc_index(p1loc) == 5 assert fm.get_frame_depth() == 6 fm.mark_as_free(p0) p2 = InputArgRef() p2loc = fm.loc(p2) assert p2loc == ploc assert len(fm.freelist) == 0 for box in fm.bindings.keys(): fm.mark_as_free(box) fm.bind(InputArgRef(), FakeFramePos(3, 'r')) assert len(fm.freelist) == 6 def test_frame_manager_basic(self): b0, b1 = newboxes(0, 1) fm = TFrameManager() 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(InputArgInt()) assert fm.get_frame_depth() == 3 # f0 = InputArgFloat() locf0 = fm.loc(f0) # can't be odd assert fm.get_loc_index(locf0) == 4 assert fm.get_frame_depth() == 6 # f1 = InputArgFloat() locf1 = fm.loc(f1) assert fm.get_loc_index(locf1) == 6 assert fm.get_frame_depth() == 8 fm.mark_as_free(b1) assert fm.freelist b2 = InputArgInt() 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 = InputArgRef() ploc = fm.loc(p0) assert fm.get_loc_index(ploc) == 0 assert fm.get_frame_depth() == 8 assert ploc != loc1 p1 = InputArgRef() p1loc = fm.loc(p1) assert fm.get_loc_index(p1loc) == 3 assert fm.get_frame_depth() == 8 fm.mark_as_free(p0) p2 = InputArgRef() p2loc = fm.loc(p2) assert p2loc == ploc assert len(fm.freelist) == 0 fm.mark_as_free(b2) f3 = InputArgFloat() fm.mark_as_free(p2) floc = fm.loc(f3) assert fm.get_loc_index(floc) == 0 for box in fm.bindings.keys(): fm.mark_as_free(box) class TestForceResultInReg(object): # use it's own class since there are so many cases def test_force_result_in_reg_1(self): # var in reg, dies b0, b1 = newboxes(0, 0) longevity = {b0: Lifetime(0, 1), b1: Lifetime(1, 3)} fm = TFrameManager() asm = MockAsm() rm = RegisterManager(longevity, frame_manager=fm, assembler=asm) rm.next_instruction() loc0 = rm.force_allocate_reg(b0) rm._check_invariants() rm.next_instruction() loc = rm.force_result_in_reg(b1, b0) assert loc is loc0 assert len(asm.moves) == 0 rm._check_invariants() def test_force_result_in_reg_2(self): # var in reg, survives b0, b1 = newboxes(0, 0) longevity = {b0: Lifetime(0, 2), b1: Lifetime(1, 3)} fm = TFrameManager() asm = MockAsm() rm = RegisterManager(longevity, frame_manager=fm, assembler=asm) rm.next_instruction() loc0 = rm.force_allocate_reg(b0) rm._check_invariants() rm.next_instruction() loc = rm.force_result_in_reg(b1, b0) assert loc is not loc0 assert rm.loc(b0) is loc0 assert len(asm.moves) == 1 rm._check_invariants() def test_force_result_in_reg_3(self): # var in reg, survives, no free registers b0, b1, b2, b3, b4 = newboxes(0, 0, 0, 0, 0) 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) rm.next_instruction() for b in b0, b1, b2, b3: rm.force_allocate_reg(b) assert not len(rm.free_regs) rm._check_invariants() rm.next_instruction() rm.force_result_in_reg(b4, b0) rm._check_invariants() assert len(asm.moves) == 1 def test_force_result_in_reg_4(self): b0, b1 = newboxes(0, 0) longevity = {b0: Lifetime(0, 1), b1: Lifetime(0, 1)} fm = TFrameManager() asm = MockAsm() rm = RegisterManager(longevity, frame_manager=fm, assembler=asm) rm.next_instruction() fm.loc(b0) rm.force_result_in_reg(b1, b0) rm._check_invariants() loc = rm.loc(b1) assert isinstance(loc, FakeReg) loc = rm.loc(b0) assert isinstance(loc, FakeFramePos) assert len(asm.moves) == 1 def test_force_result_in_reg_const(self): # const boxes, longevity = boxes_and_longevity(2) fm = TFrameManager() asm = MockAsm() rm = RegisterManager(longevity, frame_manager=fm, assembler=asm) rm.next_instruction() c = ConstInt(0) rm.force_result_in_reg(boxes[0], c) rm._check_invariants() # some tests where the result is supposed to go in a fixed register def test_force_result_in_reg_fixed_reg_1(self): # var in reg, dies b0, b1 = newboxes(0, 0) longevity = LifetimeManager({b0: Lifetime(0, 1), b1: Lifetime(1, 3)}) longevity.try_use_same_register(b0, b1) longevity.fixed_register(1, r1, b1) fm = TFrameManager() asm = MockAsm() rm = RegisterManager(longevity, frame_manager=fm, assembler=asm) rm.next_instruction() loc0 = rm.force_allocate_reg(b0) rm._check_invariants() rm.next_instruction() loc = rm.force_result_in_reg(b1, b0) assert loc is loc0 assert loc is r1 assert len(asm.moves) == 0 rm._check_invariants() def test_force_result_in_reg_fixed_reg_2(self): # var in reg, survives b0, b1 = newboxes(0, 0) longevity = LifetimeManager({b0: Lifetime(0, 2), b1: Lifetime(1, 3)}) # has no effect, lifetimes overlap longevity.try_use_same_register(b0, b1) longevity.fixed_register(1, r1, b1) fm = TFrameManager() asm = MockAsm() rm = RegisterManager(longevity, frame_manager=fm, assembler=asm) rm.next_instruction() loc0 = rm.force_allocate_reg(b0) rm._check_invariants() rm.next_instruction() loc = rm.force_result_in_reg(b1, b0) assert loc is not loc0 assert rm.loc(b0) is loc0 assert loc is r1 assert len(asm.moves) == 1 rm._check_invariants() # _____________________________________________________ # tests that assign registers in a mocked way for a fake CPU class RegisterManager2(BaseRegMan): all_regs = [r0, r1, r2, r3, r4, r5, r6, r7] save_around_call_regs = [r0, r1, r2, r3] frame_reg = r8 # calling conventions: r0 is result # r1 r2 r3 are arguments and caller-saved registers # r4 r5 r6 r7 are callee-saved registers def convert_to_imm(self, v): return v.value def call_result_location(self, v): return r0 class FakeRegalloc(BaseRegalloc): def __init__(self): self.assembler = MockAsm() def fake_prepare_loop(self, inputargs, operations, looptoken, inputarg_locs=None): operations = self._prepare(inputargs, operations, []) self.operations = operations if inputarg_locs is None: self._set_initial_bindings(inputargs, looptoken) else: for v, loc in zip(inputargs, inputarg_locs): self.rm.reg_bindings[v] = loc self.rm.free_regs.remove(loc) self.possibly_free_vars(list(inputargs)) self._add_fixed_registers() return operations def _prepare(self, inputargs, operations, allgcrefs): self.fm = TFrameManager() # compute longevity of variables longevity = compute_vars_longevity(inputargs, operations) self.longevity = longevity self.rm = RegisterManager2( longevity, assembler=self.assembler, frame_manager=self.fm) return operations def possibly_free_var(self, var): self.rm.possibly_free_var(var) def possibly_free_vars(self, vars): for var in vars: if var is not None: # xxx kludgy self.possibly_free_var(var) def possibly_free_vars_for_op(self, op): for i in range(op.numargs()): var = op.getarg(i) if var is not None: # xxx kludgy self.possibly_free_var(var) if op.type != 'v': self.possibly_free_var(op) def loc(self, x): return self.rm.loc(x) def force_allocate_reg_or_cc(self, var): assert var.type == INT if self.next_op_can_accept_cc(self.operations, self.rm.position): # hack: return the ebp location to mean "lives in CC". This # ebp will not actually be used, and the location will be freed # after the next op as usual. self.rm.force_allocate_frame_reg(var) return r8 else: # else, return a regular register (not ebp). return self.rm.force_allocate_reg(var, need_lower_byte=True) def fake_allocate(self, loop): from rpython.jit.backend.x86.jump import remap_frame_layout def emit(*args): self.assembler.emitted.append(args) for i, op in enumerate(loop.operations): self.rm.position = i opnum = op.getopnum() opname = op.getopname() if rop.is_comparison(opnum): locs = [self.loc(x) for x in op.getarglist()] loc = self.force_allocate_reg_or_cc(op) emit(opname, loc, locs) elif opname.startswith("int_"): locs = [self.loc(x) for x in op.getarglist()] loc = self.rm.force_result_in_reg( op, op.getarg(0), op.getarglist()) emit(opname, loc, locs[1:]) elif op.is_guard(): fail_locs = [self.loc(x) for x in op.getfailargs()] emit(opname, self.loc(op.getarg(0)), fail_locs) elif rop.is_call(opnum): # calling convention! src_locs = [self.loc(x) for x in op.getarglist()[1:]] self.rm.before_call() loc = self.rm.after_call(op) dst_locs = [r1, r2, r3][:len(src_locs)] remap_frame_layout(self.assembler, src_locs, dst_locs, r8) emit(opname, loc, dst_locs) elif opname == "label": descr = op.getdescr() locs = [self.loc(x) for x in op.getarglist()] emit(opname, locs) descr._fake_arglocs = locs lastop = loop.operations[-1] if lastop.getopname() == "jump" and lastop.getdescr() is descr: # now we know the places, add hints for i, r in enumerate(locs): if isinstance(r, FakeReg): self.longevity.fixed_register( len(loop.operations) - 1, r, lastop.getarg(i)) elif opname == "jump": src_locs = [self.loc(x) for x in op.getarglist()] dst_locs = op.getdescr()._fake_arglocs remap_frame_layout(self.assembler, src_locs, dst_locs, r8) emit("jump", dst_locs) else: locs = [self.loc(x) for x in op.getarglist()] if op.type != "v": loc = self.rm.force_allocate_reg(op) emit(opname, loc, locs) else: emit(opname, locs) self.possibly_free_vars_for_op(op) return self.assembler.emitted def _add_fixed_registers(self): for i, op in enumerate(self.operations): opnum = op.getopnum() opname = op.getopname() args = op.getarglist() if rop.is_call(opnum): # calling convention! arglist = op.getarglist()[1:] for arg, reg in zip(arglist + [None] * (3 - len(arglist)), [r1, r2, r3]): self.longevity.fixed_register(i, reg, arg) self.longevity.fixed_register(i, r0, op) elif opname.startswith("int_"): if not args[0].is_constant(): self.longevity.try_use_same_register(args[0], op) CPU = getcpuclass() class TestFullRegallocFakeCPU(object): # XXX copy-paste from test_regalloc_integration cpu = CPU(None, None) cpu.setup_once() targettoken = TargetToken() targettoken2 = TargetToken() fdescr1 = BasicFailDescr(1) fdescr2 = BasicFailDescr(2) fdescr3 = BasicFailDescr(3) def setup_method(self, meth): self.targettoken._ll_loop_code = 0 self.targettoken2._ll_loop_code = 0 def f1(x): return x+1 def f2(x, y): return x*y def f10(*args): assert len(args) == 10 return sum(args) F1PTR = lltype.Ptr(lltype.FuncType([lltype.Signed], lltype.Signed)) F2PTR = lltype.Ptr(lltype.FuncType([lltype.Signed]*2, lltype.Signed)) F10PTR = lltype.Ptr(lltype.FuncType([lltype.Signed]*10, lltype.Signed)) f1ptr = llhelper(F1PTR, f1) f2ptr = llhelper(F2PTR, f2) f10ptr = llhelper(F10PTR, f10) f1_calldescr = cpu.calldescrof(F1PTR.TO, F1PTR.TO.ARGS, F1PTR.TO.RESULT, EffectInfo.MOST_GENERAL) f2_calldescr = cpu.calldescrof(F2PTR.TO, F2PTR.TO.ARGS, F2PTR.TO.RESULT, EffectInfo.MOST_GENERAL) f10_calldescr = cpu.calldescrof(F10PTR.TO, F10PTR.TO.ARGS, F10PTR.TO.RESULT, EffectInfo.MOST_GENERAL) namespace = locals().copy() def parse(self, s, boxkinds=None, namespace=None): return parse(s, self.cpu, namespace or self.namespace, boxkinds=boxkinds) def allocate(self, s, inputarg_locs=None): loop = self.parse(s) self.loop = loop regalloc = FakeRegalloc() regalloc.fake_prepare_loop(loop.inputargs, loop.operations, loop.original_jitcell_token, inputarg_locs) self.regalloc = regalloc return regalloc.fake_allocate(loop) def test_simple(self): ops = ''' [i0] label(i0, descr=targettoken) i1 = int_add(i0, 1) i2 = int_lt(i1, 20) guard_true(i2) [i1] jump(i1, descr=targettoken) ''' emitted = self.allocate(ops) fp0 = FakeFramePos(0, INT) assert emitted == [ ("label", [fp0]), ("move", r0, fp0), ("int_add", r0, [1]), ("int_lt", r8, [r0, 20]), ("guard_true", r8, [r0]), ("move", fp0, r0), ("jump", [fp0]), ] def test_call(self): ops = ''' [i0] i1 = int_mul(i0, 2) i2 = call_i(ConstClass(f1ptr), i1, descr=f1_calldescr) guard_false(i2) [] ''' emitted = self.allocate(ops) fp0 = FakeFramePos(0, INT) assert emitted == [ ("move", r1, fp0), ("int_mul", r1, [2]), ("call_i", r0, [r1]), ("guard_false", r0, []), ] def test_call_2(self): ops = ''' [i0, i1] i2 = int_mul(i0, 2) i3 = int_add(i1, 1) i4 = call_i(ConstClass(f1ptr), i2, descr=f1_calldescr) guard_false(i4) [i3] ''' emitted = self.allocate(ops) fp0 = FakeFramePos(0, INT) fp1 = FakeFramePos(1, INT) assert emitted == [ ("move", r1, fp0), ("int_mul", r1, [2]), ("move", r4, fp1), # r4 gets picked since it's callee-saved ("int_add", r4, [1]), ("call_i", r0, [r1]), ("guard_false", r0, [r4]), ] def test_coalescing(self): ops = ''' [i0] i1 = int_mul(i0, 5) i5 = int_is_true(i1) guard_true(i5) [] i2 = int_mul(i0, 2) i3 = int_add(i2, 1) # i2 and i3 need to be coalesced i4 = call_i(ConstClass(f1ptr), i3, descr=f1_calldescr) guard_false(i4) [] ''' emitted = self.allocate(ops) fp0 = FakeFramePos(0, INT) assert emitted == [ ('move', r1, fp0), ('int_mul', r1, [5]), ('int_is_true', r8, [r1]), ('guard_true', r8, []), ('move', r1, fp0), ('int_mul', r1, [2]), ('int_add', r1, [1]), ('call_i', r0, [r1]), ('guard_false', r0, []) ] def test_specify_inputarg_locs(self): ops = ''' [i0] i1 = int_mul(i0, 5) i5 = int_is_true(i1) guard_true(i5) [] ''' emitted = self.allocate(ops, [r0]) assert emitted == [ ('int_mul', r0, [5]), ('int_is_true', r8, [r0]), ('guard_true', r8, []) ] def test_coalescing_first_var_already_in_different_reg(self): ops = ''' [i0] i2 = int_mul(i0, 2) i3 = int_add(i2, 1) # i2 and i3 need to be coalesced i4 = call_i(ConstClass(f1ptr), i3, descr=f1_calldescr) guard_false(i4) [i0] ''' emitted = self.allocate(ops, [r5]) assert emitted == [ ('move', r1, r5), ('int_mul', r1, [2]), ('int_add', r1, [1]), ('call_i', r0, [r1]), ('guard_false', r0, [r5]) ] def test_call_spill_furthest_use(self): # here, i2 should be spilled, because its use is farther away ops = ''' [i0, i1, i2, i3, i4, i5, i6] i8 = call_i(ConstClass(f2ptr), i0, i1, descr=f2_calldescr) escape_i(i3) escape_i(i2) guard_false(i8) [i2, i3, i4, i5, i6] ''' emitted = self.allocate(ops, [r1, r2, r0, r3, r4, r5, r6]) fp0 = FakeFramePos(0, INT) assert emitted == [ ('move', fp0, r0), ('move', r7, r3), ('call_i', r0, [r1, r2]), ('escape_i', r1, [r7]), ('escape_i', r1, [fp0]), ('guard_false', r0, [fp0, r7, r4, r5, r6]) ] @py.test.mark.skip("messy - later") def test_call_spill(self): # i0 dies, i1 is the argument, the other fight for caller-saved regs # all_regs = [r0, r1, r2, r3, r4, r5, r6, r7] # save_around_call_regs = [r0, r1, r2, r3] ops = ''' [i0, i1, i2, i3, i4, i5, i6] i8 = call_i(ConstClass(f2ptr), i1, i0, descr=f2_calldescr) guard_false(i8) [i2, i3, i4, i5, i6] ''' emitted = self.allocate(ops, [r5, r1, r0, r2, r3, r6, r7]) assert emitted == ["???"] def test_jump_hinting(self): ops = ''' [i0, i1] i2 = escape_i() i3 = escape_i() label(i2, i3, descr=targettoken) i4 = escape_i() i5 = escape_i() jump(i4, i5, descr=targettoken) ''' emitted = self.allocate(ops) assert emitted == [ ('escape_i', r0, []), ('escape_i', r1, []), ('label', [r0, r1]), ('escape_i', r0, []), ('escape_i', r1, []), ('jump', [r0, r1]) ]