Author: Remi Meier <[email protected]>
Branch: stmgc-c8
Changeset: r80975:3df49e2a17bd
Date: 2015-11-26 12:44 +0100
http://bitbucket.org/pypy/pypy/changeset/3df49e2a17bd/
Log: wip: implement generic forward data flow analysis
First requires some uses to determine if it is generic and
convenient enough
diff --git a/rpython/translator/backendopt/dataflow.py
b/rpython/translator/backendopt/dataflow.py
new file mode 100644
--- /dev/null
+++ b/rpython/translator/backendopt/dataflow.py
@@ -0,0 +1,88 @@
+from rpython.flowspace.model import mkentrymap
+
+
+
+class AbstractDataFlowAnalysis(object):
+
+ def transfer_function(self, block, in_state):
+ """Returns a new out_state after flowing the 'in_state'
+ through 'block'"""
+ raise NotImplementedError("abstract base class")
+
+ def entry_state(self, block):
+ """Returns the initial state for the 'block' with which
+ the analysis starts.
+ Forward: start block
+ Backwards: return block"""
+ raise NotImplementedError("abstract base class")
+
+ def initialize_block(self, block):
+ """Return the (default) in_state, out_state for 'block'
+ used to initialize all blocks before starting the analysis"""
+ raise NotImplementedError("abstract base class")
+
+ def join_operation(self, preds_outs, inputargs, pred_out_args):
+ """Joins all preds_outs to generate a new in_state for the
+ current block.
+ 'inputargs' is the list of input arguments to the block;
+ 'pred_out_args' is a list of lists of arguments given to
+ the link by a certain predecessor.
+ """
+ raise NotImplementedError("abstract base class")
+
+ def calculate(self, graph, entrymap=None):
+ """Run the analysis on 'graph' and return the in and
+ out states as two {block:state} dicts"""
+ raise NotImplementedError("abstract base class")
+
+
+
+
+
+class AbstractForwardDataFlowAnalysis(AbstractDataFlowAnalysis):
+
+ def _update_successor_blocks(self, block, out_state, entrymap,
+ in_states, out_states):
+ if out_states[block] == out_state:
+ return set()
+ out_states[block] = out_state
+ #
+ # update all successors
+ to_do = set()
+ for link in block.exits:
+ succ = link.target
+ # collect all out_states of predecessors:
+ preds_outs = []
+ inputargs = succ.inputargs
+ preds_out_args = [[] for _ in inputargs]
+ for link in entrymap[succ]:
+ preds_outs.append(out_states[link.prevblock])
+ for i in range(len(inputargs)):
+ preds_out_args[i].append(link.args[i])
+ block_in = self.join_operation(preds_outs, inputargs,
preds_out_args)
+ if block_in != in_states[succ]:
+ # in_state changed
+ to_do.add(succ)
+ in_states[succ] = block_in
+ return to_do
+
+
+ def calculate(self, graph, entrymap=None):
+ if entrymap is None:
+ entrymap = mkentrymap(graph)
+ in_states = {}
+ out_states = {}
+ #
+ for block in graph.iterblocks():
+ in_states[block], out_states[block] = self.initialize_block(block)
+ in_states[graph.startblock] = self.entry_state(graph.startblock)
+ #
+ # iterate:
+ pending = {graph.startblock,}
+ while pending:
+ block = pending.pop()
+ block_out = self.transfer_function(block, in_states[block])
+ pending |= self._update_successor_blocks(
+ block, block_out, entrymap, in_states, out_states)
+ #
+ return in_states, out_states
diff --git a/rpython/translator/backendopt/test/test_dataflow.py
b/rpython/translator/backendopt/test/test_dataflow.py
new file mode 100644
--- /dev/null
+++ b/rpython/translator/backendopt/test/test_dataflow.py
@@ -0,0 +1,65 @@
+import random
+from rpython.tool.algo.unionfind import UnionFind
+from rpython.translator.backendopt.dataflow import
AbstractForwardDataFlowAnalysis
+
+
+
+from rpython.translator.translator import TranslationContext, graphof
+
+
+class SimpleForwardAnalysis(AbstractForwardDataFlowAnalysis):
+ def __init__(self):
+ self.seen = set()
+
+ def transfer_function(self, block, in_state):
+ self.seen.add(block)
+ return in_state
+
+ def entry_state(self, block):
+ return True
+
+ def initialize_block(self, block):
+ return False, False
+
+ def join_operation(self, preds_outs, inputargs, pred_out_args):
+ return any(preds_outs)
+
+
+def test_simple_forward_flow():
+ def f(x):
+ if x < 0:
+ if x == -1:
+ return x+1
+ else:
+ return x+2
+ else:
+ if x == 1:
+ return x-1
+ else:
+ return x-2
+ t = TranslationContext()
+ g = t.buildflowgraph(f)
+ sfa = SimpleForwardAnalysis()
+ ins, outs = sfa.calculate(g)
+ assert len(sfa.seen) == 8
+ assert ins[g.startblock] == sfa.entry_state(None)
+ assert outs[g.returnblock] == sfa.entry_state(None)
+
+def test_loopy_forward_flow():
+ def f(x):
+ if x < 0:
+ while x:
+ pass
+ return x
+ else:
+ while x:
+ if x-1:
+ return x
+ t = TranslationContext()
+ g = t.buildflowgraph(f)
+ sfa = SimpleForwardAnalysis()
+ ins, outs = sfa.calculate(g)
+ g.show()
+ assert len(sfa.seen) == 5
+ assert ins[g.startblock] == sfa.entry_state(None)
+ assert outs[g.returnblock] == sfa.entry_state(None)
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
