Mercurial > lcfOS

annotate python/ppci/codegen/graph.py @ 337:b00219172a42

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added cool lm3s811 qemu project
author Windel Bouwman
date Thu, 20 Feb 2014 20:04:52 +0100
parents e9fe6988497c
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()
323
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
10 self.adj_map = {}
269
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
11
337
b00219172a42 Added cool lm3s811 qemu project
Windel Bouwman
parents: 323
diff changeset
12 def add_node(self, n):
277
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
13 self.nodes.add(n)
323
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
14 if n not in self.adj_map:
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
15 self.adj_map[n] = set()
277
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
16
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
17 def delNode(self, n):
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
18 self.nodes.remove(n)
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
19
269
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
20 def addEdge(self, n, m):
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
21 """ Add an edge from n to m """
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
22 self.edges.add((n, m))
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
23 self.edges.add((m, n))
323
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
24 self.adj_map[n].add(m)
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
25 self.adj_map[m].add(n)
277
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
26
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
27 def hasEdge(self, n, m):
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
28 return (n, m) in self.edges
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
29
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
30 def delEdge(self, n, m):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
31 self.edges.remove((n, m))
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
32 self.edges.remove((m, n))
269
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
33
277
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
34 def adjecent(self, n):
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
35 """ Return all nodes with edges to n """
323
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
36 return self.adj_map[n] & self.nodes
296
9417caea2eb3 Directorized some backend files
Windel Bouwman
parents: 278
diff changeset
37
269
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
38 def to_dot(self, f):
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
39 """ Generate graphviz dot representation """
296
9417caea2eb3 Directorized some backend files
Windel Bouwman
parents: 278
diff changeset
40 for n in self.nodes:
312
2c9768114877 Added cool logging formatter
Windel Bouwman
parents: 301
diff changeset
41 print(' {} [label="{}" shape=box3d];'.format(id(n), n), file=f)
269
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
42 for n, m in self.edges:
312
2c9768114877 Added cool logging formatter
Windel Bouwman
parents: 301
diff changeset
43 print(' {} -> {};'.format(id(n), id(m)), file=f)
269
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
44
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
45
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
46 class Node:
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
47 """
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
48 Node in a graph.
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
49 """
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
50 def __init__(self, g):
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents:
diff changeset
51 self.g = g
296
9417caea2eb3 Directorized some backend files
Windel Bouwman
parents: 278
diff changeset
52 self.addDegree = 0 # Hack to increase degree
277
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
53
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
54 @property
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
55 def Adjecent(self):
277
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
56 return self.g.adjecent(self)
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
57
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
58 @property
046017431c6a Started register allocator
Windel Bouwman
parents: 274
diff changeset
59 def Degree(self):
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
60 return len(self.Adjecent) + self.addDegree
270
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
61
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
62
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
63 class DiGraph(Graph):
323
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
64 """ Directed graph. """
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
65 def __init__(self):
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
66 super().__init__()
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
67 self.suc_map = {}
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
68 self.pre_map = {}
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
69
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
70 def addEdge(self, n, m):
323
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
71 """ Add a directed edge from n to m """
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
72 assert n in self.nodes
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
73 assert m in self.nodes
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
74 self.edges.add((n, m))
323
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
75 self.suc_map[n].add(m)
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
76 self.pre_map[m].add(n)
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
77 self.adj_map[n].add(m)
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
78 self.adj_map[m].add(n)
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
79
337
b00219172a42 Added cool lm3s811 qemu project
Windel Bouwman
parents: 323
diff changeset
80 def add_node(self, n):
b00219172a42 Added cool lm3s811 qemu project
Windel Bouwman
parents: 323
diff changeset
81 super().add_node(n)
323
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
82 if n not in self.suc_map:
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
83 self.suc_map[n] = set()
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
84 if n not in self.pre_map:
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
85 self.pre_map[n] = set()
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
86
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
87 def hasEdge(self, n, m):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
88 return (n, m) in self.edges
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
89
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
90 def successors(self, n):
323
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
91 return self.suc_map[n] & self.nodes
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
92
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
93 def predecessors(self, n):
323
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 312
diff changeset
94 return self.pre_map[n] & self.nodes
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
95
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
96
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
97 class DiNode(Node):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
98 @property
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
99 def Succ(self):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
100 return self.g.successors(self)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
101
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
102 @property
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
103 def Pred(self):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
104 return self.g.predecessors(self)
337
b00219172a42 Added cool lm3s811 qemu project
Windel Bouwman
parents: 323
diff changeset
105
b00219172a42 Added cool lm3s811 qemu project
Windel Bouwman
parents: 323
diff changeset
106 def __gt__(self, other):
b00219172a42 Added cool lm3s811 qemu project
Windel Bouwman
parents: 323
diff changeset
107 return self in other.Succ