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