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