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