Mercurial > codeOptimizer
changeset 4:3a56cd936c59
Cleanup some code.
Add code for breaking loops in the dependency tree.
| author | Tom Fredrik Blenning Klaussen <bfg@blenning.no> |
|---|---|
| date | Mon, 24 Sep 2012 01:16:43 +0200 |
| parents | f65c2d63ab66 |
| children | accc99f131a7 |
| files | Compilable.py Config.py DepGraph.py codeOptimizer.py |
| diffstat | 4 files changed, 124 insertions(+), 31 deletions(-) [+] |
line wrap: on
line diff
--- a/Compilable.py Sun Sep 16 21:31:41 2012 +0200 +++ b/Compilable.py Mon Sep 24 01:16:43 2012 +0200 @@ -125,3 +125,14 @@ def __repr__(self): return self.path + + + @staticmethod + def acceptsFile(name): + if name.endswith(".hpp"): + return True + if name.endswith(".h"): + return True + if name.endswith(".cpp"): + return True + return False
--- a/Config.py Sun Sep 16 21:31:41 2012 +0200 +++ b/Config.py Mon Sep 24 01:16:43 2012 +0200 @@ -27,6 +27,13 @@ def getCxxflags(self, name): value = self.getOption(self.document.childNodes[0], 'Cxxflags', name) - if not value: + if value == None: raise xml.dom.NotFoundErr() return value + + def getFiles(self): + retVal = [] + for elem in self.document.getElementsByTagName('file'): + for t in elem.childNodes: + retVal.append(t.wholeText) + return retVal
--- a/DepGraph.py Sun Sep 16 21:31:41 2012 +0200 +++ b/DepGraph.py Mon Sep 24 01:16:43 2012 +0200 @@ -1,3 +1,4 @@ +import copy, sys from types import * class DepGraph: @@ -11,14 +12,9 @@ self.values.append(value) - def addDependency(self, src, dst): - if not type(dst) is ListType: - dst = [ dst ] - + def rightSize(self): vl = len(self.values) dl = len(self.deps) - si = self.values.index(src) - if dl != vl: full = [] @@ -32,30 +28,102 @@ for i in range(0, dl): self.deps[i].append(exp[:]) - + + def addDependency(self, src, dst): + if not type(dst) is ListType: + dst = [ dst ] + + self.rightSize() + + si = self.values.index(src) for d in dst: if d in self.values: di = self.values.index(d) self.deps[si][di] = True + @staticmethod + def identifyStronglyConnectedComponents(deps): + index=0 + S=[] + vindex={} + lowlink={} + retVal=[] + for v in range(len(deps)): + if not v in vindex: + retVal.extend(DepGraph.strongconnect(deps, v, index, vindex, lowlink, S)) + return retVal + + @staticmethod + def strongconnect(deps, v, index, vindex, lowlink, S): + retVal = [] + # Set the depth index for v to the smallest unused index + vindex[v] = index + lowlink[v] = index + #print index + index += 1 + S.append(v) + + # Consider successors of v + for w in range(len(deps)): + if not deps[w][v]: + continue + if not w in vindex: + # Successor w has not yet been visited; recurse on it + res = DepGraph.strongconnect(deps, w, index, vindex, lowlink, S) + retVal.extend(res) + lowlink[v] = min(lowlink[v], lowlink[w]) + elif w in S: + # Successor w is in stack S and hence in the current SCC + lowlink[v] = min(lowlink[v], vindex[w]) + + # If v is a root node, pop the stack and generate an SCC + if lowlink[v] == vindex[v]: + #start a new strongly connected component + component = [] + w = None + while w != v: + w = S.pop() + #add w to current strongly connected component + component.append(w) + retVal.append(component) + return retVal + + @staticmethod + def dissolveStronglyConnectedComponents(deps): + dissolved = True + while dissolved: + dissolved = False + strong = DepGraph.identifyStronglyConnectedComponents(deps) + for s in strong: + if len(s) > 1: + #We remove the first dependency, and see how it goes. + v = s[0] + for w in s[1:]: + if deps[w][v]: + #print "Remove link %d -> %d" % (w, v) + deps[w][v] = False + dissolved = True + break + return deps + sys.exit(1) @staticmethod def directedGraphInternal(deps): dl = len(deps) - myVals = [] + startPoints = [] for i in range(dl): if not max(deps[i]): - myVals.append(i) + startPoints.append(i) - for i in myVals: + for i in startPoints: for j in range(dl): deps[j][i] = False - retVal = myVals + retVal = startPoints - if len(deps) != len(myVals): - subVals = self.directedGraphInternal(deps) - for val in myVals: + if len(deps) != len(startPoints): + subVals = DepGraph.directedGraphInternal(deps) + for val in startPoints: if val in subVals: ind = subVals.index(val) del subVals[ind] @@ -80,8 +148,13 @@ res += s return res - def directedGraph(self): - deps = self.deps[:][:] + def depGraphRepr(self): + return self.printableDepgraph(self.deps) + + def directedGraph(self, force = True): + deps = copy.deepcopy(self.deps) + if force: + deps = self.dissolveStronglyConnectedComponents(deps) vals = self.directedGraphInternal(deps) retVal = [] for i in vals:
--- a/codeOptimizer.py Sun Sep 16 21:31:41 2012 +0200 +++ b/codeOptimizer.py Mon Sep 24 01:16:43 2012 +0200 @@ -7,30 +7,29 @@ from Config import Config +def usage(name): + print "Usage is:\n\t%s <xml configuration file> [files for analysis]" % name -def isHppfile(name): - if name.endswith(".hpp"): - return True - if name.endswith(".h"): - return True - return False - -def isCppfile(name): - if name.endswith(".cpp"): - return True - return False +if len(sys.argv) < 2: + usage(sys.argv[0]) + sys.exit(1) try: options = Config(sys.argv[1]) except: print sys.argv[1] + ' is not a valid xml file' + sys.exit(1) + infiles = sys.argv[2:] +if not infiles: + infiles = options.getFiles() + files = {} unknown = [] for file in infiles: - if isHppfile(file) or isCppfile(file): + if Compilable.acceptsFile(file): c = Compilable(file) c.setFlags(options.getCxxflags(file)) files[file] = c @@ -47,13 +46,16 @@ depgraph.add(files[file]) for file in files: - depgraph.addDependency(files[file], files[file].dependencies()) + depgraph.addDependency(files[file], + list(files[dep] + for dep in files[file].dependencies())) files = depgraph.directedGraph() +print files for file in files: if not file.worksWithoutModifications(): - print file.path + print files[file].path raise SystemExit(file.path + " does not compile at all") for file in files: