Mercurial > lcfOS

annotate python/interferencegraph.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 2ccd57b1d78c
rev   line source
277
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
1 import graph
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
2
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
3
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
4 class InterferenceGraphNode(graph.Node):
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()
277
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
9
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
10 def __repr__(self):
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
11 return 'IGN<{}>'.format(self.temps)
277
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
12
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
13
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
14 class InterferenceGraph(graph.Graph):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
15 """
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
16 Interference graph.
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
17 """
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
18 def __init__(self, flowgraph):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
19 """
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
20 Create a new interference graph from a flowgraph
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
21 """
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
22 super().__init__()
277
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
23 # Calculate liveness in CFG:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
24 ###
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
25 # Liveness:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
26 # in[n] = use[n] UNION (out[n] - def[n])
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
27 # out[n] = for s in n.succ in union in[s]
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
28 ###
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
29 for n in flowgraph.nodes:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
30 n.live_in = set()
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
31 n.live_out = set()
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
32
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
33 # Dataflow fixed point iteration:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
34 change = True
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
35 while change:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
36 change = False
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
37 for n in flowgraph.nodes:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
38 _in = n.live_in
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
39 _out = n.live_out
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
40 n.live_in = n.uses | (n.live_out - n.defs)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
41 if n.Succ:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
42 n.live_out = set.union(*(s.live_in for s in n.Succ))
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
43 else:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
44 n.live_out = set()
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
45 change = change or (_in != n.live_in) or (_out != n.live_out)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
46
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
47 # Construct interference graph:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
48 for n in flowgraph.nodes:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
49 for tmp in n.live_out:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
50 n1 = self.getNode(tmp)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
51 for tmp2 in (n.live_out - {tmp}):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
52 n2 = self.getNode(tmp2)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
53 self.addEdge(n1, n2)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
54
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
55 def getNode(self, tmp):
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
56 # Linear search
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
57 # TODO: can be improved for speed!
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
58 for n in self.nodes:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
59 if tmp in n.temps:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
60 return n
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
61 n = InterferenceGraphNode(self, tmp)
277
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
62 self.addNode(n)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
63 return n
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
64
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
65 def Combine(self, n, m):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
66 """ Combine n and m into n """
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
67 n.temps.extend(m.temps)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
68 n.moves.update(m.moves)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
69 for t in m.Adjecent:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
70 self.addEdge(n, t)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
71 self.delNode(m)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
72