diff options
Diffstat (limited to 'scripts/maint/analyze_callgraph.py')
| -rwxr-xr-x | scripts/maint/analyze_callgraph.py | 259 |
1 files changed, 259 insertions, 0 deletions
diff --git a/scripts/maint/analyze_callgraph.py b/scripts/maint/analyze_callgraph.py new file mode 100755 index 0000000000..8ce5827f07 --- /dev/null +++ b/scripts/maint/analyze_callgraph.py @@ -0,0 +1,259 @@ +#!/usr/bin/python + +import re +import sys +import copy +import cPickle +import os + +class Parser: + def __init__(self): + self.calls = {} + self.definedIn = {} + + def enter_func(self, name): + if self.infunc and not self.extern and self.calledfns: + if self.infunc in self.definedIn: + #print "{}: {} or {}?".format( + # self.infunc, self.definedIn[self.infunc], self.module) + self.definedIn[self.infunc] = 'nil' + else: + self.definedIn[self.infunc] = self.module + self.calls.setdefault(self.infunc, set()).update( self.calledfns ) + + self.calledfns = set() + self.infunc = name + self.extern = False + + def parse_callgraph_file(self, inp, module): + self.infunc = None + self.extern = False + self.calledfns = set() + self.module = module + + for line in inp: + m = re.match(r"Call graph node for function: '([^']+)'", line) + if m: + self.enter_func(m.group(1)) + continue + m = re.match(r" CS<[^>]+> calls external node", line) + if m: + self.extern = True + m = re.match(r" CS<[^>]+> calls function '([^']+)'", line) + if m: + self.calledfns.add(m.group(1)) + self.enter_func(None) + + def extract_callgraph(self): + c = self.calls + self.calls = {} + return c + + +def transitive_closure(g): + passno = 0 + changed = True + g = copy.deepcopy(g) + import random + while changed: + passno += 1 + changed = False + keys = g.keys() + idx = 0 + for k in keys: + idx += 1 + print "Pass %d/?: %d/%d\r" %(passno, idx, len(keys)), + sys.stdout.flush() + newset = g[k].copy() + for fn in g[k]: + newset.update(g.get(fn, set())) + if len(newset) != len(g[k]): + g[k].update( newset ) + changed = True + + print + + return g + +def strongly_connected_components(g): + # From https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm, done stupidly. + index_of = {} + index = [ 0 ] + lowlink = {} + S = [] + onStack = set() + + all_sccs = [] + + def strongconnect(fn): + index_of[fn] = index[0] + lowlink[fn] = index[0] + index[0] += 1 + S.append(fn) + onStack.add(fn) + + for w in g.get(fn, []): + if w not in index_of: + strongconnect(w) + lowlink[fn] = min(lowlink[fn], lowlink[w]) + elif w in onStack: + lowlink[fn] = min(lowlink[fn], index_of[w]) + + if lowlink[fn] == index_of[fn]: + this_scc = [] + all_sccs.append(this_scc) + while True: + w = S.pop() + onStack.remove(w) + this_scc.append(w) + if w == fn: + break + + for v in g.keys(): + if v not in index_of: + strongconnect(v) + + return all_sccs + +def biggest_component(sccs): + return max(len(c) for c in sccs) + +def connection_bottlenecks(callgraph): + + callers = {} + for fn in callgraph: + for fn2 in callgraph[fn]: + callers.setdefault(fn2, set()).add(fn) + + components = strongly_connected_components(callgraph) + components.sort(key=len) + big_component_fns = components[-1] + size = len(big_component_fns) + + function_bottlenecks = fn_results = [] + + total = len(big_component_fns) + idx = 0 + for fn in big_component_fns: + idx += 1 + print "Pass 1/3: %d/%d\r"%(idx, total), + sys.stdout.flush() + cg2 = copy.deepcopy(callgraph) + del cg2[fn] + + fn_results.append( (size - biggest_component(strongly_connected_components(cg2)), fn) ) + + print + bcf_set = set(big_component_fns) + + call_bottlenecks = fn_results = [] + result_set = set() + total = len(big_component_fns) + idx = 0 + for fn in big_component_fns: + fn_callers = callers[fn].intersection(bcf_set) + idx += 1 + if len(fn_callers) != 1: + continue + + print "Pass 2/3: %d/%d\r"%(idx, total), + sys.stdout.flush() + + caller = fn_callers.pop() + assert len(fn_callers) == 0 + cg2 = copy.deepcopy(callgraph) + cg2[caller].remove(fn) + + fn_results.append( (size - biggest_component(strongly_connected_components(cg2)), fn, "called by", caller) ) + result_set.add( (caller, fn) ) + + print + + total = len(big_component_fns) + idx = 0 + for fn in big_component_fns: + fn_calls = callgraph[fn].intersection(bcf_set) + idx += 1 + if len(fn_calls) != 1: + continue + + print "Pass 3/3: %d/%d\r"%(idx, total), + sys.stdout.flush() + + callee = fn_calls.pop() + if (fn, callee) in result_set: + continue + + assert len(fn_calls) == 0 + cg2 = copy.deepcopy(callgraph) + cg2[fn].remove(callee) + + fn_results.append( (size - biggest_component(strongly_connected_components(cg2)), callee, "called by", fn) ) + + print + + + return (function_bottlenecks, call_bottlenecks) + +if __name__ == '__main__': + p = Parser() + for fname in sys.argv[1:]: + modname = re.sub(r'.*/', '', fname).replace('.callgraph', '.c') + with open(fname, 'r') as f: + p.parse_callgraph_file(f, modname) + + sys.stdout.flush() + + print "Building callgraph" + callgraph = p.extract_callgraph() + inModule = p.definedIn + + print "Deriving module callgraph" + modCallgraph = {} + for fn in callgraph: + fnMod = inModule[fn] + for called in callgraph[fn]: + try: + calledMod = inModule[called] + except KeyError: + continue + modCallgraph.setdefault(fnMod, set()).add(calledMod) + del modCallgraph['nil'] + + print "Finding strongly connected components" + sccs = strongly_connected_components(callgraph) + + print "Finding the transitive closure of the callgraph.." + closure = transitive_closure(callgraph) + + print "Finding bottlenecks..." + bottlenecks = connection_bottlenecks(callgraph) + + print "Finding module SCCs" + modSCCS = strongly_connected_components(modCallgraph) + + print "Finding module TC" + modTC = transitive_closure(modCallgraph) + + print "Finding module bottlenecks" + modB = connection_bottlenecks(modCallgraph) + + data = { + 'callgraph' : callgraph, + 'sccs' : sccs, + 'closure' : closure, + 'bottlenecks' : bottlenecks, + 'modules' : p.definedIn, + 'modItems' : { + 'callgraph' : modCallgraph, + 'sccs' : modSCCS, + 'closure' : modTC, + 'bottlenecks' : modB, + } + } + + with open('callgraph.pkl', 'w') as f: + cPickle.dump(data, f) + + + |