Mercurial > lcfOS

annotate python/ppci/codegen/interferencegraph.py @ 301:6753763d3bec

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merge codegen into ppci package
author Windel Bouwman
date Thu, 05 Dec 2013 17:02:38 +0100
parents python/codegen/interferencegraph.py@9417caea2eb3
children 04cf4d26a3bc
rev   line source
296
9417caea2eb3 Directorized some backend files
Windel Bouwman
parents: 280
diff changeset
1 from .graph import Graph, Node
277
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
2
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
3
296
9417caea2eb3 Directorized some backend files
Windel Bouwman
parents: 280
diff changeset
4 class InterferenceGraphNode(Node):
277
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
5 def __init__(self, g, varname):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
6 super().__init__(g)
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
7 self.temps = [varname]
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
8 self.moves = set()
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
9 self.color = None
277
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
10
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
11 def __repr__(self):
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
12 return '{}({})'.format(self.temps, self.color)
277
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
13
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
14
296
9417caea2eb3 Directorized some backend files
Windel Bouwman
parents: 280
diff changeset
15 class InterferenceGraph(Graph):
277
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
16 """
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
17 Interference graph.
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
18 """
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
19 def __init__(self, flowgraph):
296
9417caea2eb3 Directorized some backend files
Windel Bouwman
parents: 280
diff changeset
20 """ Create a new interference graph from a flowgraph """
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
21 super().__init__()
277
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
22 # Calculate liveness in CFG:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
23 ###
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
24 # Liveness:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
25 # in[n] = use[n] UNION (out[n] - def[n])
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
26 # out[n] = for s in n.succ in union in[s]
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
27 ###
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
28 for n in flowgraph.nodes:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
29 n.live_in = set()
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
30 n.live_out = set()
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
31
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
32 # Dataflow fixed point iteration:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
33 change = True
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
34 while change:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
35 change = False
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
36 for n in flowgraph.nodes:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
37 _in = n.live_in
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
38 _out = n.live_out
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
39 n.live_in = n.uses | (n.live_out - n.defs)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
40 if n.Succ:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
41 n.live_out = set.union(*(s.live_in for s in n.Succ))
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
42 else:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
43 n.live_out = set()
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
44 change = change or (_in != n.live_in) or (_out != n.live_out)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
45
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
46 # Construct interference graph:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
47 for n in flowgraph.nodes:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
48 for tmp in n.live_out:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
49 n1 = self.getNode(tmp)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
50 for tmp2 in (n.live_out - {tmp}):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
51 n2 = self.getNode(tmp2)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
52 self.addEdge(n1, n2)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
53
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
54 def to_dot(self, f):
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
55 """ Generate graphviz dot representation """
296
9417caea2eb3 Directorized some backend files
Windel Bouwman
parents: 280
diff changeset
56 for n in self.nodes:
9417caea2eb3 Directorized some backend files
Windel Bouwman
parents: 280
diff changeset
57 print('{} [label="{}" shape=box3d];'.format(id(n), n), file=f)
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
58 for n, m in self.edges:
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
59 print('{} -> {};'.format(id(n), id(m)), file=f)
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
60
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
61 def to_txt(self):
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
62 for node in self.nodes:
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
63 print('{} interferes: {}'.format(node, node.Adjecent))
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
64
277
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
65 def getNode(self, tmp):
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
66 # Linear search
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
67 # TODO: can be improved for speed!
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
68 for n in self.nodes:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
69 if tmp in n.temps:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
70 return n
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
71 n = InterferenceGraphNode(self, tmp)
277
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
72 self.addNode(n)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
73 return n
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
74
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
75 def Combine(self, n, m):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
76 """ Combine n and m into n """
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
77 n.temps.extend(m.temps)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
78 n.moves.update(m.moves)
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
79 # Reroute all edges:
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
80 e1 = [e for e in self.edges if e[0] is m]
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
81 e2 = [e for e in self.edges if e[1] is m]
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
82 for e in e1:
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
83 self.edges.remove(e)
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
84 self.addEdge(n, e[1])
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
85 for e in e2:
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
86 self.edges.remove(e)
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
87 self.addEdge(n, e[0])
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
88 # Remove node m:
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
89 self.delNode(m)