Mercurial > lcfOS

annotate python/ppci/codegen/interferencegraph.py @ 303:be7f60545368

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Final fixups
author Windel Bouwman
date Fri, 06 Dec 2013 12:37:48 +0100
parents 6753763d3bec
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)