inter_dataflow.py

   1 #!/usr/bin/env python3
   2 #
   3 # This script requires a callgraph, which should be constructed
   4 # e.g. with make_callgraph.sh.
   5 #
   6 import sys
   7 import os
   8 import glob
   9 import collections
  10 import copy
  11 from pprint import pprint
  12
  13 import core
  14 from parser import Parser
  15 from core import CFGPrinter, is_addr
  16 import xform_inter
  17 import progdb
  18 import arch
  19 import dot
  20 from cfgutils import save_cfg
  21 import utils
  22
  23 from utils import maybesorted
  24
  25
  26 core.Inst.annotate_calls = True
  27
  28
  29 def save_cfg_layer(cfg_layer, suffix):
  30     for name, cfg in cfg_layer.items():
  31         save_cfg(cfg, suffix)
  32
  33
  34 progdb.load_funcdb(sys.argv[1] + "/funcdb.yaml")
  35 # Load binary data
  36 import bindata
  37 bindata.init(sys.argv[1])
  38 # Load symtab
  39 if os.path.exists(sys.argv[1] + "/symtab.txt"):
  40     progdb.load_symtab(sys.argv[1] + "/symtab.txt")
  41
  42 callgraph = xform_inter.build_callgraph()
  43
  44 with open("cg-current.dot", "w") as out:
  45     dot.dot(callgraph, out, is_cfg=False)
  46
  47 #for func in callgraph.iter_rev_postorder():
  48 #    print(func, callgraph[func])
  49
  50 CFG_MAP = collections.defaultdict(dict)
  51
  52 import script_i_prepare
  53
  54 for full_name in glob.glob(sys.argv[1] + "/*.lst"):
  55     p = Parser(full_name)
  56     cfg = p.parse()
  57     cfg.parser = p
  58     #print("Loading:", cfg.props["name"])
  59     CFG_MAP["org"][cfg.props["name"]] = cfg
  60
  61     cfg2 = cfg.copy()
  62     script_i_prepare.apply(cfg2)
  63     CFG_MAP["pre"][cfg2.props["name"]] = cfg2
  64
  65     save_cfg(cfg2, ".pre")
  66
  67
  68 #print(CFG_MAP)
  69
  70 #save_cfg_layer(CFG_MAP["pre"], ".1")
  71
  72 subiter_cnt = 0
  73 update_cnt = 0
  74
  75 func_stats = collections.defaultdict(lambda: [0, 0])
  76
  77 def process_one(cg, func, xform_pass):
  78     global subiter_cnt, update_cnt
  79     upward_queue = [func]
  80     downward_queue = []
  81     cnt = 0
  82
  83     cur_queue = upward_queue
  84     while upward_queue or downward_queue:
  85         subiter_cnt += 1
  86         cnt += 1
  87         if not cur_queue:
  88             if cur_queue is upward_queue:
  89                 cur_queue = downward_queue
  90             else:
  91                 cur_queue = upward_queue
  92         func = cur_queue.pop(0)
  93
  94         print("--- Next to process: %s ---" % func)
  95         progdb.clear_updated()
  96
  97         cfg = CFG_MAP["pre"][func].copy()
  98
  99         call_lo_union = xform_inter.calc_callsites_live_out(cg, func)
 100         progdb.update_cfg_prop(cfg, "callsites_live_out", call_lo_union)
 101         print("%s: callsites_live_out set to %s" % (func, utils.repr_stable(call_lo_union)))
 102         if "modifieds" in progdb.FUNC_DB[func]:
 103             progdb.FUNC_DB[func]["returns"] = arch.ret_filter(progdb.FUNC_DB[func]["modifieds"] & call_lo_union)
 104         else:
 105             print("%s: doesn't yet have modifieds!" % func)
 106
 107         xform_pass.apply(cfg)
 108
 109         if progdb.UPDATED_FUNCS:
 110             func_stats[func][0] += 1
 111             assert len(progdb.UPDATED_FUNCS) == 1, repr(progdb.UPDATED_FUNCS)
 112             func2 = progdb.UPDATED_FUNCS.pop()
 113             assert func2 == func
 114             update_cnt += 1
 115
 116             progdb.update_funcdb(cfg)
 117             save_cfg(cfg, ".1")
 118             dot.save_dot(cfg, ".1")
 119             CFG_MAP["pre"][func].props = cfg.props
 120
 121             for x in maybesorted(cg.pred(func)):
 122                 if x not in upward_queue:
 123                     upward_queue.append(x)
 124
 125             for callee in maybesorted(cg.succ(func)):
 126                 print("! updating callee", callee)
 127                 if callee not in downward_queue:
 128                     downward_queue.append(callee)
 129
 130             print("--- Finished processing: %s ---" % func)
 131             print("# New up (caller) queue:", upward_queue)
 132             print("# New down (callee) queue:", downward_queue)
 133         else:
 134             func_stats[func][1] += 1
 135             print("%s not updated" % func)
 136             # Maybe funcdb properties not updated, but bblocks props can very well be
 137             save_cfg(cfg, ".1")
 138             dot.save_dot(cfg, ".1")
 139
 140     print("Subiters:", cnt)
 141
 142
 143 import script_i_func_params_returns
 144
 145 iter_cnt = 1
 146
 147 while True:
 148     print("=== Iteration %d ===" % iter_cnt)
 149     old_funcdb = copy.deepcopy(progdb.FUNC_DB)
 150     progdb.clear_updated()
 151
 152     # We start with some leaf node (then eventually with all the rest of
 153     # leafs). With leaf (call-less) function, we can know everything about
 154     # its parameters. So, we learn that, and then propagate this information
 155     # to all its callers, then to callers of its callers. We go in this
 156     # upward fashion (propagating parameter information) until we can, and
 157     # then we start downward motion, hoping to collect as much information
 158     # as possible about function live-outs, i.e. returns. We go in this
 159     # zig-zag fashion, until there's something to update.
 160     for e in maybesorted(callgraph.exits()):
 161         print("Processing leaf", e)
 162         process_one(callgraph, e, script_i_func_params_returns)
 163
 164     progdb.save_funcdb(sys.argv[1] + "/funcdb.yaml.out%d" % iter_cnt)
 165
 166     if progdb.FUNC_DB == old_funcdb:
 167         break
 168
 169     print("So far: %d iterations, %d sub-iterations, %d updates" % (iter_cnt, subiter_cnt, update_cnt))
 170
 171     iter_cnt += 1
 172 #    if iter_cnt > 3:
 173 #        break
 174
 175
 176 print("Done in %d iterations, %d sub-iterations, %d updates" % (iter_cnt, subiter_cnt, update_cnt))
 177
 178 pprint(func_stats)
 179 HITS = MISSES = 0
 180 for func, (hits, misses) in func_stats.items():
 181     HITS += hits
 182     MISSES += misses
 183
 184 print("Hits: %d, misses: %d, ratio: %.2f" % (HITS, MISSES, HITS / (HITS + MISSES)))