Mercurial > lcfOS

annotate python/graph.py @ 286:d9df72971cbf

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Changed package to module
author Windel Bouwman
date Fri, 15 Nov 2013 13:52:32 +0100
parents 9fca39eebe50
children
rev   line source
269
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
1
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
2 class Graph:
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
3 """
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
4 Generic graph base class.
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
5 Can dump to graphiz dot format for example!
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
6 """
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
7 def __init__(self):
277
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
8 self.nodes = set()
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
9 self.edges = set()
269
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
10
277
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
11 def addNode(self, n):
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
12 self.nodes.add(n)
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
13
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
14 def delNode(self, n):
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
15 self.nodes.remove(n)
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
16
269
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
17 def addEdge(self, n, m):
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
18 """ Add an edge from n to m """
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
19 self.edges.add((n, m))
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
20 self.edges.add((m, n))
277
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
21
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
22 def hasEdge(self, n, m):
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
23 return (n, m) in self.edges
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
24
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
25 def delEdge(self, n, m):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
26 self.edges.remove((n, m))
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
27 self.edges.remove((m, n))
269
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
28
277
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
29 def adjecent(self, n):
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
30 """ Return all nodes with edges to n """
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
31 # TODO: this can be optimized for speed:
277
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
32 return set(m for m in self.nodes if self.hasEdge(n, m))
269
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
33
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
34 def to_dot(self, f):
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
35 """ Generate graphviz dot representation """
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
36 for node in self.nodes:
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
37 print('{} [label="{}" shape=box3d];'.format(id(node), node), file=f)
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
38 for n, m in self.edges:
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
39 print('{} -> {};'.format(id(n), id(m)), file=f)
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
40
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
41
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
42 class Node:
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
43 """
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
44 Node in a graph.
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
45 """
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
46 def __init__(self, g):
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
47 self.g = g
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
48 self.addDegree = 0 # Hack to increase degree
277
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
49
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
50 @property
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
51 def Adjecent(self):
277
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
52 return self.g.adjecent(self)
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
53
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
54 @property
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
55 def Degree(self):
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
56 return len(self.Adjecent) + self.addDegree
270
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
57
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
58
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
59 class DiGraph(Graph):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
60 """
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
61 Directed graph.
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
62 """
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
63 def addEdge(self, n, m):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
64 """ Add an edge from n to m """
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
65 self.edges.add((n, m))
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
66
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
67 def hasEdge(self, n, m):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
68 return (n, m) in self.edges
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
69
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
70 def successors(self, n):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
71 return set(m for m in self.nodes if self.hasEdge(n, m))
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
72
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
73 def predecessors(self, n):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
74 return set(m for m in self.nodes if self.hasEdge(m, n))
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
75
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
76
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
77 class DiNode(Node):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
78 @property
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
79 def Succ(self):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
80 return self.g.successors(self)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
81
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
82 @property
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
83 def Pred(self):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
84 return self.g.predecessors(self)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
85