message: Try generalizing dataflow
diff: @@ -2,32 +2,51 @@ import sys
  import json
  from form_blocks import form_blocks
  import cfg
  +from collections import namedtuple
  +# A single dataflow analysis consists of these part:
  +# - forward: True for forward, False for backward.
  +# - init: An initial value (bottom or top of the latice).
  +# - merge: Take a list of values and produce a single value.
  +# - transfer: The transfer function.
  +Analysis = namedtuple('Analysis', ['forward', 'init', 'merge', 'transfer'])
  -def df_worklist(blocks, bottom, merge, transfer):
  +
  +def df_worklist(blocks, analysis):
  preds, succs = cfg.edges(blocks)
  - entry = list(blocks.keys())[0]
  +
  + # Switch between directions.
  + if analysis.forward:
  + first_block = list(blocks.keys())[0] # Entry.
  + in_edges = preds
  + out_edges = succs
  + else:
  + first_block = list(blocks.keys())[-1] # Exit.
  + in_edges = succs
  + out_edges = preds
  # Initialize.
  - invals = {entry: bottom}
  - outvals = {node: bottom for node in blocks}
  - worklist = list(blocks.keys())
  + in_ = {first_block: analysis.init}
  + out = {node: analysis.init for node in blocks}
  # Iterate.
  + worklist = list(blocks.keys())
  while worklist:
  node = worklist.pop(0)
  - inval = merge(outvals[n] for n in preds[node])
  - invals[node] = inval
  + inval = analysis.merge(out[n] for n in in_edges[node])
  + in_[node] = inval
  - outval = transfer(blocks[node], inval)
  + outval = analysis.transfer(blocks[node], inval)
  - if outval != outvals[node]:
  - outvals[node] = outval
  - worklist += succs[node]
  + if outval != out[node]:
  + out[node] = outval
  + worklist += out_edges[node]
  - print(invals)
  - print(outvals)
  + if analysis.forward:
  + return in_, out
  + else:
  + return out, in_
  def gen(block):
  @@ -38,28 +57,36 @@ def kill(block):
  return {i['dest'] for i in block if 'dest' in i}
  -def _union(sets):
  +def union(sets):
  out = set()
  for s in sets:
  out.update(s)
  return out
  +ANALYSES = {
  + 'defined': Analysis(
  + True,
  + init=set(),
  + merge=union,
  + transfer=lambda block, in_: gen(block).union(in_ - kill(block)),
  + )
  +}
  +
  +
  def run_df(bril):
  for func in bril['functions']:
  # Form the CFG.
  blocks = cfg.block_map(form_blocks(func['instrs']))
  cfg.add_terminators(blocks)
  - df_worklist(
  - blocks,
  - bottom=set(),
  - merge=_union,
  - transfer=lambda block, in_: gen(block).union(in_ - kill(block)),
  - )
  + in_, out = df_worklist(blocks, ANALYSES['defined'])
  + for block in blocks:
  + print('{}:', block)
  + print(' in: ', in_[block])
  + print(' out:', out[block])
  if __name__ == '__main__':
  bril = json.load(sys.stdin)
  run_df(bril)
  - json.dump(bril, sys.stdout, indent=2, sort_keys=True)
  