Mercurial > lcfOS

comparison 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
comparison
equal deleted inserted replaced
277:046017431c6a 278:9fca39eebe50
2 2
3 3
4 class InterferenceGraphNode(graph.Node): 4 class InterferenceGraphNode(graph.Node):
5 def __init__(self, g, varname): 5 def __init__(self, g, varname):
6 super().__init__(g) 6 super().__init__(g)
7 self.varname = varname 7 self.temps = [varname]
8 self.moves = set()
8 9
9 def __repr__(self): 10 def __repr__(self):
10 return '{}'.format(self.varname) 11 return 'IGN<{}>'.format(self.temps)
11 12
12 13
13 class InterferenceGraph(graph.Graph): 14 class InterferenceGraph(graph.Graph):
14 """ 15 """
15 Interference graph. 16 Interference graph.
16 """ 17 """
17 def __init__(self, flowgraph): 18 def __init__(self, flowgraph):
18 """ 19 """
19 Create a new interference graph from a flowgraph 20 Create a new interference graph from a flowgraph
20 """ 21 """
21 super().__init__(False) 22 super().__init__()
22 # Mapping from node to live set
23 self.liveMap = {}
24 self.tempMap = {}
25 # Calculate liveness in CFG: 23 # Calculate liveness in CFG:
26 ### 24 ###
27 # Liveness: 25 # Liveness:
28 # in[n] = use[n] UNION (out[n] - def[n]) 26 # in[n] = use[n] UNION (out[n] - def[n])
29 # out[n] = for s in n.succ in union in[s] 27 # out[n] = for s in n.succ in union in[s]
53 for tmp2 in (n.live_out - {tmp}): 51 for tmp2 in (n.live_out - {tmp}):
54 n2 = self.getNode(tmp2) 52 n2 = self.getNode(tmp2)
55 self.addEdge(n1, n2) 53 self.addEdge(n1, n2)
56 54
57 def getNode(self, tmp): 55 def getNode(self, tmp):
58 if tmp not in self.tempMap: 56 # Linear search
59 self.tempMap[tmp] = self.newNode(tmp) 57 # TODO: can be improved for speed!
60 return self.tempMap[tmp] 58 for n in self.nodes:
61 59 if tmp in n.temps:
62 def newNode(self, varname): 60 return n
63 n = InterferenceGraphNode(self, varname) 61 n = InterferenceGraphNode(self, tmp)
64 self.addNode(n) 62 self.addNode(n)
65 return n 63 return n
66 64
67 def combine(self, n, m): 65 def Combine(self, n, m):
68 self.nodes.remove(m) 66 """ Combine n and m into n """
69 n.varnames.extend(m.varnames) 67 n.temps.extend(m.temps)
68 n.moves.update(m.moves)
69 for t in m.Adjecent:
70 self.addEdge(n, t)
71 self.delNode(m)
72