Mercurial > lcfOS

annotate python/graph.py @ 278:9fca39eebe50

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
First implementation of regalloc with coalsesc
author Windel Bouwman
date Sun, 29 Sep 2013 14:08:15 +0200
parents 046017431c6a
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