1# * Copyright 2016, NICTA 2# * 3# * This software may be distributed and modified according to the terms 4# of 5# * the BSD 2-Clause license. Note that NO WARRANTY is provided. 6# * See "LICENSE_BSD2.txt" for details. 7# * 8# * @TAG(NICTA_BSD) 9 10import pydot 11import re 12import graph_refine.problem as problem 13from elf_file import elfFile, isSpecIns 14 15#functions f called 16def gFuncsCalled(f,fs,ignore_funs): 17 g = fs[elfFile().gFunName(f)] 18 call_node_indexes = [x for x in g.nodes if g.nodes[x].kind == 'Call'] 19 call_targs = [g.nodes[x].get_args()[0] for x in call_node_indexes] 20 #rid clone subfixes 21 call_targs = [x.split('.')[0] for x in call_targs] 22 call_targs = [x for x in call_targs if x not in ignore_funs] 23 24 return list(set(call_targs)) 25 26def funsCallGraph(funs,dir_name,ignore_funs): 27 #dict to dicts of fun to funcs called 28 cg = {} 29 ignore_funs = ignore_funs + [f for f in funs if isSpecIns(f)] 30 for f in funs: 31 if isSpecIns(f): 32 continue 33 cg[f] = gFuncsCalled(f,funs,ignore_funs) 34 return cg 35 36def nFuncsFuncsCall(call_graph): 37 ret = {} 38 for f in call_graph: 39 l = len(call_graph[f]) 40 if l not in ret: 41 ret[l] = [] 42 ret[l].append(f) 43 return ret 44 45def dotCallGraph(fun,cg,dir_name): 46 graph = pydot.Dot(graph_type='digraph') 47 #graph.set_overlap('scale') 48 nodes = {} 49 50 callers = [] 51 vs = [fun] 52 seen = [] 53 while vs: 54 #print "vs: %s" % vs 55 f = vs.pop() 56 if f in seen: 57 continue 58 seen.append(f) 59 callers += cg[f] 60 callers.append(f) 61 vs += cg[f] 62 63 callers = set(callers) 64 65 for f in callers: 66 nodes[f] = pydot.Node(f) 67 graph.add_node(nodes[f]) 68 69 n_edges = 0 70 for f in callers: 71 #now add edges 72 for ff in cg[f]: 73 if ff not in nodes: 74 nodes[ff] = pydot.Node(ff,Nodestyle="dotted") 75 graph.add_node(nodes[ff]) 76 assert nodes[f] 77 assert nodes[ff] 78 graph.add_edge(pydot.Edge(nodes[f],nodes[ff])) 79 n_edges += 1 80 81 print 'emitting call graph for %s' % fun 82 print '%d nodes %d edges' % (len(nodes), n_edges) 83 #graph.write_raw('%s/graphs/call_graph_%s.dot' % (dir_name,fun)) 84 #print '.raw generated' 85 graph.write_svg('%s/graphs/call_graph_%s.svg' % (dir_name,fun)) 86 87def makeCallGraph(fun,functions,dir_name): 88 cg = funsCallGraph(functions,dir_name,[]) 89 dotCallGraph(fun,cg,dir_name) 90 91#return a list of all funcs transitively called by f 92def transitivelyCalled(f,cg): 93 ret = set() 94 vs = list(cg[f]) # copy the list 95 #print ' cg[%s] : %s' % (f, cg[f]) 96 while vs: 97 ff = elfFile().gFunName(vs.pop()) 98 assert '.' not in ff 99 if ff not in ret and not isSpecIns(ff): 100 ret.add(ff) 101 vs += cg[ff] 102 return ret 103 104#whether fun transtively calls one of fs_interested 105def transitivelyCallsInterested(fun, cg, fs_interested): 106 tc = transitivelyCalled(fun, cg) 107 return (fun in fs_interested) or len([x for x in fs_interested if x in tc]) != 0 108 109def drawFunCallGraph(f,funs,dn,ignore_funs,transitive=False, fs_interested=None): 110 funs = {x: funs[x] for x in funs if not x.startswith("Kernel_C")} 111 cg = funsCallGraph(funs,dn,ignore_funs) 112 tc = transitivelyCalled(f,cg) 113 if transitive: 114 cg_tc = {x:transitivelyCalled(x,cg) for x in tc +[f]} 115 else: 116 #cg_tc = {x:cg[x] for x in tc + [f]} 117 cg_tc = cg 118 if fs_interested: 119 cg_tc = {\ 120 caller: filter(lambda f: transitivelyCallsInterested(f, cg, fs_interested), cg_tc[caller]) \ 121 for caller in cg_tc if transitivelyCallsInterested(caller, cg, fs_interested)} 122 123 dotCallGraph(f,cg_tc,dn) 124 return cg_tc 125 126#return a dict of dicts of fun to transitively called funcs 127def transitiveCallGraph(funs,dn,ignore_funs): 128 ret = {} 129 cg = funsCallGraph(funs,dn,ignore_funs) 130 for f in cg: 131 ret[f] = transitivelyCalled(f,cg) 132 return ret 133 134#dict of number of transitively called functions to caller functions 135def nFuncsFuncsTranCall(funs,dn,ignore_funs): 136 tc = transitiveCallGraph(funs,dn,ignore_funs) 137 return nFuncsFuncsCall(tc) 138 139