1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
#!/usr/bin/python
import re
import sys
import copy
import cPickle
import os
class Parser:
def __init__(self):
self.calls = {}
def enter_func(self, name):
if self.infunc and not self.extern:
self.calls.setdefault(self.infunc, set()).update( self.calledfns )
self.calledfns = set()
self.infunc = name
self.extern = False
def parse_callgraph_file(self, inp):
self.infunc = None
self.extern = False
self.calledfns = set()
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):
changed = True
g = copy.deepcopy(g)
while changed:
changed = False
print "X"
for k in g.keys():
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
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
if __name__ == '__main__':
p = Parser()
for fname in sys.argv[1:]:
with open(fname, 'r') as f:
p.parse_callgraph_file(f)
callgraph = p.extract_callgraph()
sccs = strongly_connected_components(callgraph)
closure = transitive_closure(callgraph)
with open('callgraph.pkl', 'w') as f:
cPickle.dump(callgraph, f)
with open('callgraph_closure.pkl', 'w') as f:
cPickle.dump(closure, f)
with open('callgraph_sccs.pkl', 'w') as f:
cPickle.dump(sccs, f)
|
