Commits

Hakan Ardo  committed 77e3e26

In case of conflicts, prioritize among the potential short ops that can
produce one specific box instead of duplicating recursivly every op that
uses that box as an argument. The priority order is:
- ops found in the original trace
- synthetic ops (setfields converted to getfields)
- inputargs
- potential ops that was never promoted to short_boxes
This makes the effect of the optimizations less random and should always
remove loop invariant ops. Non loop invariant cases can still benefit from
unrolling but in exactly what situations has become more complicated.

  • Participants
  • Parent commits f299e69
  • Branches jit-duplicated_short_boxes

Comments (0)

Files changed (5)

File pypy/jit/metainterp/optimizeopt/heap.py

                         result = newresult
                     getop = ResOperation(rop.GETFIELD_GC, [op.getarg(0)],
                                          result, op.getdescr())
-                    getop = shortboxes.add_potential(getop)
-                    self._cached_fields_getfield_op[structvalue] = getop
-                    self._cached_fields[structvalue] = optimizer.getvalue(result)
+                    shortboxes.add_potential(getop, synthetic=True)
                 elif op.result is not None:
                     shortboxes.add_potential(op)
 

File pypy/jit/metainterp/optimizeopt/test/test_optimizeopt.py

         jump(p5, p6)
         """
         expected = """
-        [p5, p6, i12, i13, i10]
+        [p5, p6, i14, i12, i10]
+        i13 = int_add(i14, 7)
         call(i12, i13, descr=nonwritedescr)
         setfield_gc(p6, i10, descr=nextdescr)        
-        jump(p5, p6, i12, i12, i10)
+        jump(p5, p6, i10, i12, i10)
         """
         self.optimize_loop(ops, expected)
         
         jump(i1, i3)
         """
         expected = """
-        [i1, i3, i20, i18]
-        i26 = int_add(i20, i20)
-        call(i26, descr=nonwritedescr)
-        jump(i1, i18, i20, i18)
-        """
-        self.optimize_loop(ops, expected)
-
+        [i1, i2, i6, i3]
+        call(i6, descr=nonwritedescr)
+        jump(i1, i3, i6, i3)
+        """
+        short = """
+        [i1, i2]
+        i3 = int_add(i1, i1)
+        i4 = int_add(i3, i3)
+        i5 = int_add(i4, i4)
+        i6 = int_add(i5, i5)
+        jump(i1, i2, i6, i3)
+        """
+        self.optimize_loop(ops, expected, expected_short=short)
+
+    def test_prioritize_getfield1(self):
+        ops = """
+        [p1, p2]
+        i1 = getfield_gc(p1, descr=valuedescr)
+        setfield_gc(p2, i1, descr=nextdescr)
+        i2 = int_neg(i1)
+        call(i2, descr=nonwritedescr)
+        jump(p1, p2)
+        """
+        expected = """
+        [p1, p2, i2, i1]
+        call(i2, descr=nonwritedescr)
+        setfield_gc(p2, i1, descr=nextdescr)        
+        jump(p1, p2, i2, i1)
+        """
+        self.optimize_loop(ops, expected)
+
+    def test_prioritize_getfield2(self):
+        # Same as previous, but with descrs intercahnged which means
+        # that the getfield is discovered first when looking for
+        # potential short boxes during tests
+        ops = """
+        [p1, p2]
+        i1 = getfield_gc(p1, descr=nextdescr)
+        setfield_gc(p2, i1, descr=valuedescr)
+        i2 = int_neg(i1)
+        call(i2, descr=nonwritedescr)
+        jump(p1, p2)
+        """
+        expected = """
+        [p1, p2, i2, i1]
+        call(i2, descr=nonwritedescr)
+        setfield_gc(p2, i1, descr=valuedescr)        
+        jump(p1, p2, i2, i1)
+        """
+        self.optimize_loop(ops, expected)
+        
 class TestLLtype(OptimizeOptTest, LLtypeMixin):
     pass
         

File pypy/jit/metainterp/optimizeopt/unroll.py

                 args = ", ".join([logops.repr_of_arg(arg) for arg in short_inputargs])
                 debug_print('short inputargs: ' + args)
                 self.short_boxes.debug_print(logops)
+                
 
             # Force virtuals amoung the jump_args of the preamble to get the
             # operations needed to setup the proper state of those virtuals

File pypy/jit/metainterp/optimizeopt/virtualstate.py

 class ShortBoxes(object):
     def __init__(self, optimizer, surviving_boxes):
         self.potential_ops = {}
-        self.duplicates = {}
+        self.alternatives = {}
+        self.synthetic = {}
         self.aliases = {}
+        self.rename = {}
         self.optimizer = optimizer
         for box in surviving_boxes:
             self.potential_ops[box] = None
                 self.produce_short_preamble_box(box)
             except BoxNotProducable:
                 pass
-        self.duplicate_short_boxes_if_needed()
 
+    def prioritized_alternatives(self, box):
+        if box not in self.alternatives:
+            return [self.potential_ops[box]]
+        alts = self.alternatives[box]
+        hi, lo = 0, len(alts) - 1
+        while hi < lo:
+            if alts[lo] is None: # Inputarg, lowest priority
+                alts[lo], alts[-1] = alts[-1], alts[lo]
+                lo -= 1
+            elif alts[lo] not in self.synthetic: # Hi priority
+                alts[hi], alts[lo] = alts[lo], alts[hi]
+                hi += 1
+            else: # Low priority
+                lo -= 1
+        return alts
+            
+    def renamed(self, box):
+        if box in self.rename:
+            return self.rename[box]
+        return box
+    
+    def add_to_short(self, box, op):
+        if op:
+            op = op.clone()
+            for i in range(op.numargs()):
+                op.setarg(i, self.renamed(op.getarg(i)))
+        if box in self.short_boxes:
+            if op is None:
+                oldop = self.short_boxes[box].clone()
+                oldres = oldop.result
+                newbox = oldop.result = oldres.clonebox()
+                self.rename[box] = newbox
+                self.short_boxes[box] = None
+                self.short_boxes[newbox] = oldop
+            else:
+                newop = op.clone()
+                newbox = newop.result = op.result.clonebox()
+                self.short_boxes[newop.result] = newop
+            value = self.optimizer.getvalue(box)
+            self.optimizer.make_equal_to(newbox, value)
+        else:
+            self.short_boxes[box] = op
+        
     def produce_short_preamble_box(self, box):
         if box in self.short_boxes:
             return 
         if isinstance(box, Const):
             return 
         if box in self.potential_ops:
-            op = self.potential_ops[box]
-            if op:
-                for arg in op.getarglist():
-                    self.produce_short_preamble_box(arg)
-            self.short_boxes[box] = op
+            ops = self.prioritized_alternatives(box)
+            produced_one = False
+            for op in ops:
+                try:
+                    if op:
+                        for arg in op.getarglist():
+                            self.produce_short_preamble_box(arg)
+                except BoxNotProducable:
+                    pass
+                else:
+                    produced_one = True
+                    self.add_to_short(box, op)
+            if not produced_one:
+                raise BoxNotProducable
         else:
             raise BoxNotProducable
 
-    def add_potential(self, op):
+    def add_potential(self, op, synthetic=False):
         if op.result not in self.potential_ops:
             self.potential_ops[op.result] = op
-            return op
-        return self.duplicate(self.potential_ops, op)
+        else:
+            if op.result not in self.alternatives:
+                self.alternatives[op.result] = [self.potential_ops[op.result]]
+            self.alternatives[op.result].append(op)
+        if synthetic:
+            self.synthetic[op] = True
 
     def duplicate(self, destination, op):
         newop = op.clone()

File pypy/jit/metainterp/test/test_virtualstate.py

         int_ops = int_add.values() + int_neg.values()
         assert len(set([op.result for op in int_ops])) == 8
         
+    def test_prioritize1(self):
+        class Optimizer(FakeOptimizer):
+            def produce_potential_short_preamble_ops(_self, sb):
+                sb.add_potential(ResOperation(rop.GETFIELD_GC, [self.p1], self.i1))
+                sb.add_potential(ResOperation(rop.GETFIELD_GC, [self.p2], self.i1))
+                sb.add_potential(ResOperation(rop.INT_NEG, [self.i1], self.i2))
+        sb = ShortBoxes(Optimizer(), [self.p1, self.p2])
+        assert len(sb.short_boxes.values()) == 5
+        int_neg = [op for op in sb.short_boxes.values()
+                   if op and op.getopnum() == rop.INT_NEG]
+        assert len(int_neg) == 1
+        int_neg = int_neg[0]
+        getfield = [op for op in sb.short_boxes.values()
+                    if op and op.result == int_neg.getarg(0)]
+        assert len(getfield) == 1
+        assert getfield[0].getarg(0) == self.p1
+        
+    def test_prioritize2(self):
+        class Optimizer(FakeOptimizer):
+            def produce_potential_short_preamble_ops(_self, sb):
+                sb.add_potential(ResOperation(rop.GETFIELD_GC, [self.p1], self.i1),
+                                 synthetic=True)
+                sb.add_potential(ResOperation(rop.GETFIELD_GC, [self.p2], self.i1))
+                sb.add_potential(ResOperation(rop.INT_NEG, [self.i1], self.i2))
+        sb = ShortBoxes(Optimizer(), [self.p1, self.p2])
+        assert len(sb.short_boxes.values()) == 5
+        int_neg = [op for op in sb.short_boxes.values()
+                   if op and op.getopnum() == rop.INT_NEG]
+        assert len(int_neg) == 1
+        int_neg = int_neg[0]
+        getfield = [op for op in sb.short_boxes.values()
+                    if op and op.result == int_neg.getarg(0)]
+        assert len(getfield) == 1
+        assert getfield[0].getarg(0) == self.p2
+        
+    def test_prioritize3(self):
+        class Optimizer(FakeOptimizer):
+            def produce_potential_short_preamble_ops(_self, sb):
+                sb.add_potential(ResOperation(rop.GETFIELD_GC, [self.p1], self.i1))
+                sb.add_potential(ResOperation(rop.GETFIELD_GC, [self.p2], self.i1),
+                                 synthetic=True)
+                sb.add_potential(ResOperation(rop.INT_NEG, [self.i1], self.i2))
+        sb = ShortBoxes(Optimizer(), [self.p1, self.p2])
+        assert len(sb.short_boxes.values()) == 5
+        int_neg = [op for op in sb.short_boxes.values()
+                   if op and op.getopnum() == rop.INT_NEG]
+        assert len(int_neg) == 1
+        int_neg = int_neg[0]
+        getfield = [op for op in sb.short_boxes.values()
+                    if op and op.result == int_neg.getarg(0)]
+        assert len(getfield) == 1
+        assert getfield[0].getarg(0) == self.p1