Author: Remi Meier <[email protected]>
Branch: stmgc-c8
Changeset: r80888:6882bd53ee96
Date: 2015-11-24 15:55 +0100
http://bitbucket.org/pypy/pypy/changeset/6882bd53ee96/
Log: add analysis for better write barrier placement
Adds a class that looks for write/set-operations that do not require
a write barrier since the target already had a barrier executed on
all paths to these operations or the target is freshly allocated
(with no can-collect inbetween).
diff --git a/rpython/memory/gctransform/framework.py
b/rpython/memory/gctransform/framework.py
--- a/rpython/memory/gctransform/framework.py
+++ b/rpython/memory/gctransform/framework.py
@@ -52,6 +52,147 @@
return (op.opname in LL_OPERATIONS and
LL_OPERATIONS[op.opname].canmallocgc)
+
+class WriteBarrierCollector(object):
+ """
+ This class implements a forward data flow analysis to find all
+ set/write-operations in the graph that do *not* require a
+ barrier, either because they are freshly allocated or they
+ just had a barrier-requiring operation before them.
+ """
+
+ def __init__(self, graph, collect_analyzer):
+ self.graph = graph
+ self.collect_analyzer = collect_analyzer
+ self.clean_ops = set()
+ self._in_states = {} # block->state of each inputarg
+ self._out_states = {} # block->writable dict
+ self.in_stm_ignored = False
+
+ def _merge_out_states(self, out_states):
+ assert out_states
+ # True: writeable or fresh, otherwise False
+ result = [True] * len(out_states[0])
+ for outset in out_states:
+ for i, state in enumerate(outset):
+ result[i] = result[i] and state
+ return result
+
+ def _set_into_gc_array_part(self, op):
+ if op.opname == 'setarrayitem':
+ return op.args[1]
+ if op.opname == 'setinteriorfield':
+ for v in op.args[1:-1]:
+ if v.concretetype is not lltype.Void:
+ return v
+ return None
+
+ def _flow_through_block(self, block):
+ # get all out_state of predecessors and recalculate
+ # the in_state of our block (except for startblock)
+ insets = self._in_states
+ #
+ # get input variables and their states:
+ writeable = {}
+ for v, state in zip(block.inputargs, insets[block]):
+ writeable[v] = state
+ #
+ # flow through block and inspect operations that
+ # need a write barrier, and those that create new
+ # objects
+ for i, op in enumerate(block.operations):
+ if self.collect_analyzer.analyze(op): # incl. malloc, obviously
+ # clear all writeable status
+ writeable = {}
+ #
+ if op.opname == "stm_ignored_start":
+ self.in_stm_ignored = True
+ elif op.opname == "stm_ignored_stop":
+ self.in_stm_ignored = False
+ elif op.opname == "malloc":
+ rtti = get_rtti(op.args[0].value)
+ if rtti is not None and hasattr(rtti._obj,
'destructor_funcptr'):
+ # XXX: not sure why that matters, copied from
+ # find_initializing_stores
+ continue
+ writeable[op.result] = True
+ #
+ elif op.opname in ("cast_pointer", "same_as"):
+ if writeable.get(op.args[0], False):
+ writeable[op.result] = True
+ #
+ elif op.opname in ('setfield', 'setarrayitem', 'setinteriorfield',
'raw_store'):
+ if op.args[-1].concretetype == lltype.Void:
+ self.clean_ops.add(op)
+ continue # ignore setfields of Void type
+ elif not var_needsgc(op.args[0]):
+ if (var_needsgc(op.args[-1]) and
+ 'is_excdata' not in op.args[0].concretetype.TO._hints):
+ raise Exception("%s: GC pointer written into a non-GC
location"
+ % (op,))
+ self.clean_ops.add(op)
+ continue
+ elif self.in_stm_ignored:
+ # detect if we're inside a 'stm_ignored' block and in
+ # that case don't call stm_write(). This only works for
+ # writing non-GC pointers.
+ if var_needsgc(op.args[-1]):
+ raise Exception("in stm_ignored block: write of a gc
pointer")
+ self.clean_ops.add(op)
+ continue
+ elif self._set_into_gc_array_part(op) is None:
+ # full write barrier required
+ if writeable.get(op.args[0], False):
+ # already writeable, this op is also clean
+ self.clean_ops.add(op)
+ elif op in self.clean_ops:
+ # we require an stm_write
+ self.clean_ops.remove(op)
+ # always writeable after this op
+ writeable[op.args[0]] = True
+ else:
+ # things that need partial write barriers (card marking)
+ assert op not in self.clean_ops
+ #
+ # update in_states of all successors
+ updated = set()
+ for link in block.exits:
+ succ = link.target
+ outset = [writeable.get(v, False) for v in link.args]
+ if succ in insets:
+ to_merge = [insets[succ], outset]
+ new = self._merge_out_states(to_merge)
+ if new != insets[succ]:
+ updated.add(succ)
+ insets[succ] = new
+ else:
+ # block not processed yet
+ insets[succ] = outset
+ updated.add(succ)
+ return updated
+
+
+ def collect(self):
+ assert not self.clean_ops
+ assert not self.in_stm_ignored
+ # we implement a forward-flow analysis that determines the
+ # operations that do NOT need a write barrier
+ graph = self.graph
+ #
+ # initialize blocks
+ self._in_states = {}
+ self._in_states[graph.startblock] = [False] *
len(graph.startblock.inputargs)
+ #
+ # fixpoint iteration
+ # XXX: reverse postorder traversal
+ pending = {graph.startblock,}
+ while pending:
+ block = pending.pop()
+ pending |= self._flow_through_block(block)
+
+
+
+
def propagate_no_write_barrier_needed(result, block, mallocvars,
collect_analyzer, entrymap,
startindex=0):
@@ -730,9 +871,14 @@
if self.write_barrier_ptr:
from rpython.flowspace.model import mkentrymap
self._entrymap = mkentrymap(graph)
- self.clean_sets = (
- find_initializing_stores(self.collect_analyzer, graph,
- self._entrymap))
+ if self.translator.config.translation.stm:
+ wbc = WriteBarrierCollector(graph, self.collect_analyzer)
+ wbc.collect()
+ self.clean_sets = wbc.clean_ops
+ else:
+ self.clean_sets = (
+ find_initializing_stores(self.collect_analyzer, graph,
+ self._entrymap))
if self.gcdata.gc.can_optimize_clean_setarrayitems():
self.clean_sets = self.clean_sets.union(
find_clean_setarrayitems(self.collect_analyzer, graph))
diff --git a/rpython/memory/gctransform/test/test_framework.py
b/rpython/memory/gctransform/test/test_framework.py
--- a/rpython/memory/gctransform/test/test_framework.py
+++ b/rpython/memory/gctransform/test/test_framework.py
@@ -4,8 +4,9 @@
from rpython.rtyper.lltypesystem import lltype, rffi
from rpython.rtyper.lltypesystem.lloperation import llop
from rpython.memory.gc.semispace import SemiSpaceGC
-from rpython.memory.gctransform.framework import (CollectAnalyzer,
- find_initializing_stores, find_clean_setarrayitems)
+from rpython.memory.gctransform.framework import (
+ CollectAnalyzer, WriteBarrierCollector,
+ find_initializing_stores, find_clean_setarrayitems)
from rpython.memory.gctransform.shadowstack import (
ShadowStackFrameworkGCTransformer)
from rpython.memory.gctransform.test.test_transform import rtype
@@ -253,7 +254,7 @@
Constant('b', lltype.Void), varoftype(PTR_TYPE2)],
varoftype(lltype.Void)))
-def test_remove_duplicate_write_barrier():
+def test_remove_duplicate_write_barrier(gc="minimark"):
from rpython.translator.c.genc import CStandaloneBuilder
from rpython.flowspace.model import summary
@@ -272,17 +273,59 @@
f(glob_a_2, 0)
return 0
t = rtype(g, [s_list_of_strings])
- t.config.translation.gc = "minimark"
+ if gc == "stmgc":
+ t.config.translation.stm = True
+ gcpolicy = StmFrameworkGcPolicy
+ else:
+ gcpolicy = FrameworkGcPolicy2
+ t.config.translation.gc = gc
cbuild = CStandaloneBuilder(t, g, t.config,
- gcpolicy=FrameworkGcPolicy2)
+ gcpolicy=gcpolicy)
db = cbuild.generate_graphs_for_llinterp()
ff = graphof(t, f)
#ff.show()
- assert summary(ff)['direct_call'] == 1 # only one remember_young_pointer
+ if gc == "stmgc":
+ assert summary(ff)['stm_write'] == 1
+ else:
+ assert summary(ff)['direct_call'] == 1 # only one
remember_young_pointer
-def test_find_initializing_stores():
+def test_remove_duplicate_write_barrier_stm():
+ test_remove_duplicate_write_barrier("stmgc")
+def test_remove_write_barrier_stm():
+ from rpython.translator.c.genc import CStandaloneBuilder
+ from rpython.flowspace.model import summary
+
+ class A: pass
+ glob = A()
+ glob2 = A()
+ def f(n, g):
+ i = 0
+ g.a = n
+ while i < n:
+ g.a = i
+ i += 1
+ def g(argv):
+ if argv[1]:
+ f(int(argv[1]), glob)
+ else:
+ f(int(argv[1]), glob2)
+ return 0
+
+ t = rtype(g, [s_list_of_strings])
+ t.config.translation.stm = True
+ gcpolicy = StmFrameworkGcPolicy
+ t.config.translation.gc = "stmgc"
+ cbuild = CStandaloneBuilder(t, g, t.config,
+ gcpolicy=gcpolicy)
+ db = cbuild.generate_graphs_for_llinterp()
+
+ ff = graphof(t, f)
+ ff.show()
+ assert summary(ff)['stm_write'] == 1 # only one remember_young_pointer
+
+def test_write_barrier_collector():
class A(object):
pass
class B(object):
@@ -293,15 +336,19 @@
b.a = a
b.b = 1
t = rtype(f, [])
+ t.config.translation.stm = True
+ #gcpolicy = StmFrameworkGcPolicy
+ t.config.translation.gc = "stmgc"
etrafo = ExceptionTransformer(t)
graphs = etrafo.transform_completely()
collect_analyzer = CollectAnalyzer(t)
- init_stores = find_initializing_stores(collect_analyzer, t.graphs[0],
- mkentrymap(t.graphs[0]))
- assert len(init_stores) == 4
-def test_find_initializing_stores_across_blocks():
+ wbc = WriteBarrierCollector(t.graphs[0], collect_analyzer)
+ wbc.collect()
+ print wbc.clean_ops
+ assert len(wbc.clean_ops) == 4
+def test_write_barrier_collector_across_blocks():
class A(object):
pass
class B(object):
@@ -319,12 +366,82 @@
b.c = a1
b.b = a2
t = rtype(f, [int])
+ t.config.translation.stm = True
+ #gcpolicy = StmFrameworkGcPolicy
+ t.config.translation.gc = "stmgc"
etrafo = ExceptionTransformer(t)
graphs = etrafo.transform_completely()
collect_analyzer = CollectAnalyzer(t)
- init_stores = find_initializing_stores(collect_analyzer, t.graphs[0],
- mkentrymap(t.graphs[0]))
- assert len(init_stores) == 9
+
+ wbc = WriteBarrierCollector(t.graphs[0], collect_analyzer)
+ wbc.collect()
+ print "\n".join(map(str,wbc.clean_ops))
+ assert len(wbc.clean_ops) == 9
+
+def test_write_barrier_collector_blocks_merging():
+ class A(object):
+ pass
+ class B(object):
+ pass
+ def f(x):
+ a1 = A()
+ a2 = A()
+ a = A()
+ b = B()
+ b.a = a
+ if x:
+ b.b = a1
+ b.c = a2
+ else:
+ b.c = a1
+ b.b = a2
+ a.c = a2 # WB
+ b.c = a1
+ a.c = a1 # WB
+ a.b = a2
+ t = rtype(f, [int])
+ t.config.translation.stm = True
+ #gcpolicy = StmFrameworkGcPolicy
+ t.config.translation.gc = "stmgc"
+ etrafo = ExceptionTransformer(t)
+ graphs = etrafo.transform_completely()
+ collect_analyzer = CollectAnalyzer(t)
+
+ wbc = WriteBarrierCollector(t.graphs[0], collect_analyzer)
+ wbc.collect()
+ print "\n".join(map(str,wbc.clean_ops))
+ assert len(wbc.clean_ops) == 11
+
+def test_write_barrier_collector_loops():
+ class A(object):
+ pass
+ class B(object):
+ pass
+ def f(x):
+ a1 = A()
+ a2 = A()
+ a = A()
+ b = B()
+ b.a = a
+ while x:
+ b.b = a1
+ a.c = a2
+ b.c = a1
+ a.c = a1
+ t = rtype(f, [int])
+ t.config.translation.stm = True
+ #gcpolicy = StmFrameworkGcPolicy
+ t.config.translation.gc = "stmgc"
+ etrafo = ExceptionTransformer(t)
+ graphs = etrafo.transform_completely()
+ collect_analyzer = CollectAnalyzer(t)
+
+ wbc = WriteBarrierCollector(t.graphs[0], collect_analyzer)
+ wbc.collect()
+ print "\n".join(map(str,wbc.clean_ops))
+ assert len(wbc.clean_ops) == 7
+
+
def test_find_clean_setarrayitems():
S = lltype.GcStruct('S')
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
