Mercurial > lcfOS

annotate python/ppci/codegen/graph.py @ 321:8c569fbe60e4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Load yacc and burg dynamic
author Windel Bouwman
date Sun, 19 Jan 2014 18:48:45 +0100
parents 2c9768114877
children e9fe6988497c
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))
296
9417caea2eb3 Directorized some backend files
Windel Bouwman
parents: 278
diff changeset
33
269
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 """
296
9417caea2eb3 Directorized some backend files
Windel Bouwman
parents: 278
diff changeset
36 for n in self.nodes:
312
2c9768114877 Added cool logging formatter
Windel Bouwman
parents: 301
diff changeset
37 print(' {} [label="{}" shape=box3d];'.format(id(n), n), file=f)
269
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
38 for n, m in self.edges:
312
2c9768114877 Added cool logging formatter
Windel Bouwman
parents: 301
diff changeset
39 print(' {} -> {};'.format(id(n), id(m)), file=f)
269
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
296
9417caea2eb3 Directorized some backend files
Windel Bouwman
parents: 278
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)