Commits

Hakan Ardo committed 9b3ef86

- Retraces now inherits the values from the bridge producing them.
- Short preamble now created by enum_forced_boxes and from
optimizer.producer and there is no need to figgure out when it is
safe to reorder resops (work in progress, only VirtalValue's
support).
- GUARD_NONNULL's emitted for boxes where box.nonnull() is True if
needed to call a loop instead of retracing.
- Guards emitted for boxes if box.getint() layes within the required
intebount if needed to call a loop instead of retracing.

Comments (0)

Files changed (5)

pypy/jit/metainterp/optimizeopt/optimizer.py

 
     def __init__(self, box, level=None, known_class=None, intbound=None):
         self.box = box
-        self.level = level
+        if level is not None:
+            self.level = level
         self.known_class = known_class
         if intbound:
             self.intbound = intbound
     def get_key_box(self):
         return self.box
 
-    def enum_forced_boxes(self, boxes, already_seen):
+    def enum_forced_boxes(self, boxes, already_seen, shortops):
         key = self.get_key_box()
         if key not in already_seen:
             boxes.append(self.force_box())
         self.posponedop = None
         self.exception_might_have_happened = False
         self.newoperations = []
+        if self.loop.inputvalues:
+            self.setup_inputstate()
         self.set_optimizations(optimizations)
 
-
+    def setup_inputstate(self):
+        valuemap = {}
+        assert len(self.loop.inputvalues) == len(self.loop.inputargs)
+        for i in range(len(self.loop.inputvalues)):
+            value = self.loop.inputvalues[i].get_cloned(self, valuemap)
+            self.make_equal_to(self.loop.inputargs[i], value)
+        
     def set_optimizations(self, optimizations):
         if optimizations:
             self.first_optimization = optimizations[0]

pypy/jit/metainterp/optimizeopt/unroll.py

 from pypy.rlib.debug import debug_start, debug_stop, debug_print
 from pypy.jit.metainterp.optimizeutil import InvalidLoop, RetraceLoop
 from pypy.jit.metainterp.jitexc import JitException
-from pypy.jit.metainterp.history import make_hashable_int
+from pypy.jit.metainterp.history import make_hashable_int, BoxPtr
 from pypy.jit.codewriter.effectinfo import EffectInfo
 
 # Assumptions
         assert len(self.state) == len(other.state)
         for i in range(len(self.state)):
             if not self.state[i].generalization_of(other.state[i]):
+                print 'Fails on element: %d'%i
                 return False
         return True
 
             self.state[i].generate_guards(other.state[i], args[i],
                                           cpu, extra_guards)
 
+    def __repr__(self):
+        return "VirtualState:\n" + "\n".join(["  "+str(s) for s in self.state])
+
 class VirtualStateAdder(resume.ResumeDataVirtualAdder):
     def __init__(self, optimizer):
         self.fieldboxes = {}
     def _generate_guards(self, other, box, cpu, extra_guards):
         if not isinstance(other, NotVirtualInfo):
             raise InvalidLoop
+
         if self.level == LEVEL_KNOWNCLASS and \
-           box.nonnull() and \
-           self.known_class.same_constant(cpu.ts.cls_of_box(box)):
+               box.nonnull() and \
+               self.known_class.same_constant(cpu.ts.cls_of_box(box)):
             # Note: This is only a hint on what the class of box was
             # during the trace. There are actually no guarentees that this
             # box realy comes from a trace. The hint is used here to choose
             op = ResOperation(rop.GUARD_CLASS, [box, self.known_class], None)
             extra_guards.append(op)
             return
+
+        if self.level == LEVEL_NONNULL and \
+               other.level == LEVEL_UNKNOWN and \
+               isinstance(box, BoxPtr) and \
+               box.nonnull():
+            op = ResOperation(rop.GUARD_NONNULL, [box], None)
+            extra_guards.append(op)
+            return
+        
+        if self.level == LEVEL_UNKNOWN and \
+               other.level == LEVEL_UNKNOWN and \
+               isinstance(box, BoxInt) and \
+               self.intbound.contains(box.getint()):
+            if self.intbound.has_lower:
+                bound = self.intbound.lower
+                if not (other.intbound.has_lower and \
+                        other.intbound.lower >= bound):
+                    res = BoxInt()
+                    op = ResOperation(rop.INT_GE, [box, ConstInt(bound)], res)
+                    extra_guards.append(op)
+                    op = ResOperation(rop.GUARD_TRUE, [res], None)
+                    extra_guards.append(op)
+            if self.intbound.has_upper:
+                bound = self.intbound.upper
+                if not (other.intbound.has_upper and \
+                        other.intbound.upper <= bound):
+                    res = BoxInt()
+                    op = ResOperation(rop.INT_LE, [box, ConstInt(bound)], res)
+                    extra_guards.append(op)
+                    op = ResOperation(rop.GUARD_TRUE, [res], None)
+                    extra_guards.append(op)
+            return
+            
         # Remaining cases are probably not interesting
         raise InvalidLoop
         if self.level == LEVEL_CONSTANT:
             import pdb; pdb.set_trace()
             raise NotImplementedError
+
+    def __repr__(self):
+        l = {LEVEL_UNKNOWN: 'Unknonw',
+             LEVEL_NONNULL: 'NonNull',
+             LEVEL_KNOWNCLASS: 'KnownClass',
+             LEVEL_CONSTANT: 'Constant',
+             None: 'None'}[self.level]
+        return 'NotVirtualInfo(' + l + ', ' + str(self.intbound) + ')'
         
 
 class UnrollOptimizer(Optimization):
             modifier = VirtualStateAdder(self.optimizer)
             virtual_state = modifier.get_virtual_state(jump_args)
 
+            self.short_operations = []
+            self.boxes_seen_in_short = {}
+            for a in loop.preamble.inputargs:
+                self.boxes_seen_in_short[a] = True
+
             loop.preamble.operations = self.optimizer.newoperations
             self.optimizer = self.optimizer.reconstruct_for_next_iteration()
             inputargs = self.inline(self.cloned_operations,
             jmp = ResOperation(rop.JUMP, loop.inputargs[:], None)
             jmp.setdescr(loop.token)
             loop.preamble.operations.append(jmp)
+            if self.short_operations is not None:
+                self.short_operations.append(jmp)
 
             loop.operations = self.optimizer.newoperations
 
                 new_snapshot_args = []
                 for a in snapshot_args:
                     if not isinstance(a, Const):
-                        a = loop.preamble.inputargs[jump_args.index(a)]
+                        #a = loop.preamble.inputargs[jump_args.index(a)]
+                        a = self.getvalue(a).get_key_box()
                     new_snapshot_args.append(a)
                 snapshot.boxes = new_snapshot_args
                 snapshot = snapshot.prev
-
-            short = self.create_short_preamble(loop.preamble, loop)
-            if short:
+                
+            #short = self.create_short_preamble(loop.preamble, loop)
+            short = self.short_operations
+            if short is not None:
                 if False:
                     # FIXME: This should save some memory but requires
                     # a lot of tests to be fixed...
                         short[i] = op
 
                 short_loop = TreeLoop('short preamble')
-                short_loop.inputargs = loop.preamble.inputargs[:]
+                #short_loop.inputargs = loop.preamble.inputargs[:]
+                short_loop.inputargs = [self.getvalue(b).get_key_box() for b in jump_args]
                 short_loop.operations = short
 
                 # Clone ops and boxes to get private versions and 
                 ops = [inliner.inline_op(op) for op in short_loop.operations]
                 short_loop.operations = ops
                 descr = start_resumedescr.clone_if_mutable()
+                #self.inliner.inline_descr_inplace(descr)
                 inliner.inline_descr_inplace(descr)
                 short_loop.start_resumedescr = descr
 
                 for op in short_loop.operations:
                     if op.result:
                         op.result.forget_value()
-                
-    def inline(self, loop_operations, loop_args, jump_args):
-        self.inliner = inliner = Inliner(loop_args, jump_args)
-           
-        for v in self.optimizer.values.values():
-            v.last_guard_index = -1 # FIXME: Are there any more indexes stored?
 
+    def enum_forced_boxes(self, jump_args, short):
         inputargs = []
         seen_inputargs = {}
         for arg in jump_args:
             boxes = []
-            self.getvalue(arg).enum_forced_boxes(boxes, seen_inputargs)
+            self.getvalue(arg).enum_forced_boxes(boxes, seen_inputargs, short)
             for a in boxes:
                 if not isinstance(a, Const):
                     inputargs.append(a)
+        return inputargs
+        
+    def inline(self, loop_operations, loop_args, jump_args):
+
+        # FIXME: Move this to recreate_for_next_iteration
+        for v in self.optimizer.values.values():
+            v.last_guard_index = -1 # FIXME: Are there any more indexes stored?
+
+        boxes = {}
+        for i in range(len(loop_args)):
+            if loop_args[i] is jump_args[i]:
+                value = self.getvalue(loop_args[i])
+                value.enum_forced_boxes([], boxes, [])
+        passing = boxes.keys()
+        self.inliner = inliner = Inliner(loop_args + passing,
+                                         jump_args + passing)
+
+        inputargs = self.enum_forced_boxes(jump_args, self.short_operations)
 
         # This loop is equivalent to the main optimization loop in
         # Optimizer.propagate_all_forward
                 if not isinstance(a, Const) and not a in boxes_created_this_iteration:
                     if a not in inputargs:
                         inputargs.append(a)
+                        self.produce_box_in_short_preamble(a)
                         box = inliner.inline_arg(a)
                         if box in self.optimizer.values:
                             box = self.optimizer.values[box].force_box()
 
         return True
 
+    def produce_box_in_short_preamble(self, box):
+        if box in self.boxes_seen_in_short or isinstance(box, Const):
+            return
+        if self.short_operations is None:
+            return
+        self.boxes_seen_in_short[box] = True
+        op = self.optimizer.producer[box]
+
+        ok = False
+        if op.is_always_pure() or op.is_ovf():
+            ok = True
+            # FIXME: Allow getitems if they are still in the heap cache
+        elif op.getopnum() == rop.CALL:
+            effectinfo = op.getdescr().get_extra_info()
+            if effectinfo.extraeffect == EffectInfo.EF_LOOPINVARIANT:
+                ok = True
+            if effectinfo.extraeffect == EffectInfo.EF_PURE:
+                ok = True
+        if ok:
+            for arg in op.getarglist():
+                self.produce_box_in_short_preamble(arg)
+            if self.short_operations is not None:
+                self.short_operations.append(op)
+        else:
+            self.short_operations = None
+        
     def create_short_preamble(self, preamble, loop):
         #return None # Dissable
 
                 args = op.getarglist()
                 modifier = VirtualStateAdder(self.optimizer)
                 virtual_state = modifier.get_virtual_state(args)
+                print
+                print
+                print 'Lookup: ', virtual_state
+                print
+                
                 for sh in short:
                     ok = False
                     extra_guards = []
+                    print sh.virtual_state
+                    print
                     if sh.virtual_state.generalization_of(virtual_state):
                         ok = True
                     else:
                             jumpop = self.optimizer.newoperations.pop()
                             assert jumpop.getopnum() == rop.JUMP
                             for guard in extra_guards:
-                                descr = sh.start_resumedescr.clone_if_mutable()
-                                self.inliner.inline_descr_inplace(descr)
-                                guard.setdescr(descr)
+                                if guard.is_guard():
+                                    descr = sh.start_resumedescr.clone_if_mutable()
+                                    self.inliner.inline_descr_inplace(descr)
+                                    guard.setdescr(descr)
                                 self.emit_operation(guard)
                             self.optimizer.newoperations.append(jumpop)
                         return
                 if descr.failed_states:
                     retraced_count += len(descr.failed_states)
                 limit = self.optimizer.metainterp_sd.warmrunnerdesc.memory_manager.retrace_limit
-                if not self.retrace and retraced_count<limit:
+                if not self.retrace and (retraced_count<limit or limit<0):
                     if not descr.failed_states:
                         raise RetraceLoop
                     for failed in descr.failed_states:

pypy/jit/metainterp/optimizeopt/virtualize.py

                 fieldvalue = self._fields[ofs]
                 fieldvalue.get_args_for_fail(modifier)
 
-    def enum_forced_boxes(self, boxes, already_seen):
+    def enum_forced_boxes(self, boxes, already_seen, shortops):
         key = self.get_key_box()
         if key in already_seen:
             return
         if self.box is None:
             lst = self._get_field_descr_list()
             for ofs in lst:
-                self._fields[ofs].enum_forced_boxes(boxes, already_seen)
+                op = ResOperation(rop.GETFIELD_GC, [key],
+                                  self._fields[ofs].get_key_box(), ofs)
+                shortops.append(op)
+                self._fields[ofs].enum_forced_boxes(boxes, already_seen,
+                                                    shortops)
         else:
             boxes.append(self.box)
 

pypy/jit/metainterp/resume.py

     def _generalization_of(self, other):
         raise NotImplementedError
 
-
 class VirtualInfo(AbstractVirtualStructInfo):
     def __init__(self, known_class, fielddescrs):
         AbstractVirtualStructInfo.__init__(self, fielddescrs)
         if not self.known_class.same_constant(other.known_class):
             return False
         return True
+
+    def __repr__(self):
+        return 'VirtualInfo(' + str(self.known_class) + ')'
         
 
 class VStructInfo(AbstractVirtualStructInfo):

pypy/jit/metainterp/test/test_basic.py

                           'int_add': 1, 'int_sub': 1, 'int_gt': 1,
                           'jump': 1})
 
+    def test_loop_invariant_mul2(self):
+        myjitdriver = JitDriver(greens = [], reds = ['y', 'res', 'x'])
+        def f(x, y):
+            res = 0
+            while y > 0:
+                myjitdriver.can_enter_jit(x=x, y=y, res=res)
+                myjitdriver.jit_merge_point(x=x, y=y, res=res)
+                res += x * x + 2 * x
+                y -= 1
+            return res
+        res = self.meta_interp(f, [6, 7])
+        assert res == f(6, 7)
+        self.check_loop_count(1)
+        self.check_loops({'guard_true': 1,
+                          'int_add': 1, 'int_sub': 1, 'int_gt': 1,
+                          'jump': 1})
+
     def test_loop_invariant_mul_ovf(self):
         myjitdriver = JitDriver(greens = [], reds = ['y', 'res', 'x'])
         def f(x, y):
         res = self.meta_interp(f, [6, 32])
         assert res == 1167
         self.check_loop_count(3)
-        self.check_loops({'int_add': 3, 'int_lt': 2,
+        self.check_loops({'int_add': 3, 'int_lt': 1,
                           'int_sub': 2, 'guard_false': 1,
                           'jump': 2,
-                          'int_gt': 1, 'guard_true': 2})
+                          'int_gt': 1, 'guard_true': 1})
 
 
     def test_loop_invariant_mul_bridge_maintaining2(self):
         res = self.meta_interp(f, [6, 32])
         assert res == 1692
         self.check_loop_count(3)
-        self.check_loops({'int_add': 3, 'int_lt': 2,
+        self.check_loops({'int_add': 3, 'int_lt': 1,
                           'int_sub': 2, 'guard_false': 1,
                           'jump': 2,
-                          'int_gt': 1, 'guard_true': 2})
+                          'int_gt': 1, 'guard_true': 1})
 
     def test_loop_invariant_mul_bridge_maintaining3(self):
         myjitdriver = JitDriver(greens = [], reds = ['y', 'res', 'x', 'm'])
             return x
         res = self.meta_interp(f, [299], listops=True)
         assert res == f(299)
-        self.check_loops(guard_class=0, guard_value=2)        
-        self.check_loops(guard_class=0, guard_value=5, everywhere=True)
+        self.check_loops(guard_class=0, guard_value=3)        
+        self.check_loops(guard_class=0, guard_value=6, everywhere=True)
 
     def test_merge_guardnonnull_guardclass(self):
         from pypy.rlib.objectmodel import instantiate
             return x
         res = self.meta_interp(f, [299], listops=True)
         assert res == f(299)
-        self.check_loops(guard_class=0, guard_nonnull=0,
-                         guard_nonnull_class=2, guard_isnull=0)
-        self.check_loops(guard_class=0, guard_nonnull=0,
-                         guard_nonnull_class=4, guard_isnull=1,
-                         everywhere=True)
+        # There will be 1 guard_nonnull on l at the end of each bridge
+        # as the bridges don't inhert that information from the loop
+        self.check_loops(guard_class=0, guard_nonnull=2,
+                         guard_nonnull_class=2, guard_isnull=1)
 
     def test_merge_guardnonnull_guardvalue(self):
         from pypy.rlib.objectmodel import instantiate
             return x
         res = self.meta_interp(f, [299], listops=True)
         assert res == f(299)
-        self.check_loops(guard_class=0, guard_nonnull=0, guard_value=1,
+        # There will be 1 guard_nonnull on l at the end of each bridge
+        # as the bridges don't inhert that information from the loop
+        self.check_loops(guard_class=0, guard_nonnull=2, guard_value=2,
                          guard_nonnull_class=0, guard_isnull=1)
-        self.check_loops(guard_class=0, guard_nonnull=0, guard_value=3,
-                         guard_nonnull_class=0, guard_isnull=2,
-                         everywhere=True)
 
     def test_merge_guardnonnull_guardvalue_2(self):
         from pypy.rlib.objectmodel import instantiate
             return x
         res = self.meta_interp(f, [299], listops=True)
         assert res == f(299)
-        self.check_loops(guard_class=0, guard_nonnull=0, guard_value=2,
-                         guard_nonnull_class=0, guard_isnull=0)
-        self.check_loops(guard_class=0, guard_nonnull=0, guard_value=4,
-                         guard_nonnull_class=0, guard_isnull=1,
-                         everywhere=True)
+        # There will be 1 guard_nonnull on l at the end of each bridge
+        # as the bridges don't inhert that information from the loop
+        self.check_loops(guard_class=0, guard_nonnull=2, guard_value=2,
+                         guard_nonnull_class=0, guard_isnull=1)
 
     def test_merge_guardnonnull_guardclass_guardvalue(self):
         from pypy.rlib.objectmodel import instantiate
             return x
         res = self.meta_interp(f, [399], listops=True)
         assert res == f(399)
-        self.check_loops(guard_class=0, guard_nonnull=0, guard_value=2,
-                         guard_nonnull_class=0, guard_isnull=0)
-        self.check_loops(guard_class=0, guard_nonnull=0, guard_value=5,
-                         guard_nonnull_class=0, guard_isnull=1,
-                         everywhere=True)
+        # There will be 1 guard_nonnull on l at the end of each bridge
+        # as the bridges don't inhert that information from the loop
+        self.check_loops(guard_class=0, guard_nonnull=3, guard_value=3,
+                         guard_nonnull_class=0, guard_isnull=1)
 
     def test_residual_call_doesnt_lose_info(self):
         myjitdriver = JitDriver(greens = [], reds = ['x', 'y', 'l'])
                           'int_add': 1, 'int_mul': 1, 'int_sub': 2,
                           'int_gt': 2, 'jump': 2})
 
-    def test_multiple_specialied_versions_array(self):
+    def test_multiple_specialied_versions_array1(self):
         myjitdriver = JitDriver(greens = [], reds = ['idx', 'y', 'x', 'res',
                                                      'array'])
         class Base:
         res = self.meta_interp(g, [6, 14])
         assert res == g(6, 14)
         self.check_loop_count(9)
-        self.check_loops(getarrayitem_gc=6, everywhere=True)
+        self.check_loops(getarrayitem_gc=8, everywhere=True)
+        self.check_loops(getarrayitem_gc=4);
+
+    def test_multiple_specialied_versions_array2(self):
+        myjitdriver = JitDriver(greens = [], reds = ['idx', 'n', 'm', 'y', 'x',
+                                                     'res', 'array'])
+        class Base:
+            def __init__(self, val):
+                self.val = val
+        class A(Base):
+            def binop(self, other):
+                return A(self.val + other.val)
+        class B(Base):
+            def binop(self, other):
+                return B(self.val - other.val)
+        def f(x, y, n, m):
+            res = x
+            array = [1, 2, 3]
+            array[1] = 7
+            idx = 0
+            while y > m:
+                myjitdriver.can_enter_jit(idx=idx, y=y, x=x, res=res,
+                                          array=array, n=n, m=m)
+                myjitdriver.jit_merge_point(idx=idx, y=y, x=x, res=res,
+                                            array=array, n=n, m=m)
+                res = res.binop(x)
+                res.val += array[idx] + array[1]
+                if y < n:
+                    idx = 2
+                y -= 1
+            return res
+        def g(x, y, m):
+            a1 = f(A(x), y, y/2, m)
+            a2 = f(A(x), y, y/2, m)
+            b1 = f(B(x), y, y/2, m)
+            b2 = f(B(x), y, y/2, m)
+            assert a1.val == a2.val
+            assert b1.val == b2.val
+            return a1.val + b1.val
+        res = self.meta_interp(g, [6, 28, 0])
+        assert res == g(6, 28, 0)
+        self.check_loop_count(9)
+        self.check_loops(getarrayitem_gc=12, everywhere=True)
+        self.check_loops(getarrayitem_gc=4)
 
     def test_multiple_specialied_versions_bridge(self):
         myjitdriver = JitDriver(greens = [], reds = ['y', 'x', 'z', 'res'])
         res = self.meta_interp(g, [3, 23])
         assert res == 7068153
         self.check_loop_count(6)
-        self.check_loops(guard_true=4, guard_class=0, int_add=2, int_mul=2,
+        self.check_loops(guard_true=5, guard_class=0, int_add=2, int_mul=2,
                          guard_false=2)
 
     def test_dont_trace_every_iteration(self):