Mercurial > codeOptimizer

annotate DepGraph.py @ 0:28b636105ed6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Working version of codeOptimizer. -Still needs to implement more finegrained control per file basis. -CXXFLAGS are hardcoded.
author Tom Fredrik Blenning Klaussen <bfg@blenning.no>
date Sat, 15 Sep 2012 20:34:39 +0200
parents
children a1224150b8f6
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
1 import numpy
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
2
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
3 from types import *
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
4
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
5 class DepGraph:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
6 def __init__(self):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
7 self.deps = []
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
8 self.values = []
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
9
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
10 def add(self, value):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
11 if value in self.values:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
12 raise ValueError
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
13 self.values.append(value)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
14
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
15
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
16 def addDependency(self, src, dst):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
17 if not type(dst) is ListType:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
18 dst = [ dst ]
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
19
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
20 vl = len(self.values)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
21 dl = len(self.deps)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
22 si = self.values.index(src)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
23
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
24
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
25 if dl != vl:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
26 full = []
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
27 for i in range(0, vl):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
28 full.append(False)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
29
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
30 exp = []
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
31 for i in range(dl, vl):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
32 exp.append(False)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
33 self.deps.append(full[:])
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
34
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
35 for i in range(0, dl):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
36 self.deps[i].append(exp[:])
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
37
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
38 for d in dst:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
39 if d in self.values:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
40 di = self.values.index(d)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
41 self.deps[si][di] = True
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
42
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
43
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
44 @staticmethod
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
45 def directedGraphInternal(deps):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
46 dl = len(deps)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
47 myVals = []
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
48 for i in range(dl):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
49 if not max(deps[i]):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
50 myVals.append(i)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
51
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
52 for i in myVals:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
53 for j in range(dl):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
54 deps[j][i] = False
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
55
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
56 retVal = myVals
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
57
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
58 if len(deps) != len(myVals):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
59 subVals = self.directedGraphInternal(deps)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
60 for val in myVals:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
61 if val in subVals:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
62 ind = subVals.index(val)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
63 del subVals[ind]
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
64
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
65 if subVals:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
66 retVal.extend(subVals)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
67
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
68 return retVal
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
69
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
70 @staticmethod
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
71 def printableDepgraph(deps):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
72 res=''
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
73 for i in range(len(deps)):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
74 if res:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
75 res += '\n'
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
76 s = ''
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
77 for j in range(len(deps[i])):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
78 if deps[i][j]:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
79 s += '1'
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
80 else:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
81 s += '0'
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
82 res += s
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
83 return res
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
84
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
85 def directedGraph(self):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
86 deps = self.deps[:][:]
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
87 vals = self.directedGraphInternal(deps)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
88 retVal = []
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
89 for i in vals:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
90 retVal.append(self.values[i])
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
91 return retVal
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
92
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
93
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
94 def toplevelDependencies(self):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
95 dl = len(self.deps)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
96 retVal = []
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
97 for i in range(dl):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
98 if not max(self.deps[i]):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
99 print max(self.deps[i])
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
100 retVal.append(self.values[i])
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
101 return retVal