Mercurial > lcfOS
annotate python/ppci/codegen/interferencegraph.py @ 341:4d204f6f7d4e devel
Rewrite of assembler parts
| author | Windel Bouwman |
|---|---|
| date | Fri, 28 Feb 2014 18:07:14 +0100 |
| parents | b00219172a42 |
| children | 39bf68bf1891 |
| rev | line source |
|---|---|
| 337 | 1 import logging |
| 296 | 2 from .graph import Graph, Node |
| 277 | 3 |
| 4 | |
| 296 | 5 class InterferenceGraphNode(Node): |
| 277 | 6 def __init__(self, g, varname): |
| 7 super().__init__(g) | |
|
278
9fca39eebe50
First implementation of regalloc with coalsesc
Windel Bouwman
parents:
277
diff
changeset
|
8 self.temps = [varname] |
|
9fca39eebe50
First implementation of regalloc with coalsesc
Windel Bouwman
parents:
277
diff
changeset
|
9 self.moves = set() |
| 279 | 10 self.color = None |
| 277 | 11 |
| 12 def __repr__(self): | |
| 279 | 13 return '{}({})'.format(self.temps, self.color) |
| 277 | 14 |
| 15 | |
| 296 | 16 class InterferenceGraph(Graph): |
| 277 | 17 """ |
| 18 Interference graph. | |
| 19 """ | |
| 20 def __init__(self, flowgraph): | |
| 296 | 21 """ Create a new interference graph from a flowgraph """ |
|
278
9fca39eebe50
First implementation of regalloc with coalsesc
Windel Bouwman
parents:
277
diff
changeset
|
22 super().__init__() |
| 337 | 23 self.logger = logging.getLogger('interferencegraph') |
| 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 | |
| 337 | 34 # Sort flowgraph nodes backwards: |
| 35 cfg_nodes = list(flowgraph.nodes) | |
| 36 self.logger.debug('CFG nodes: {}'.format(cfg_nodes)) | |
| 37 cfg_nodes.sort(reverse=True) | |
| 38 | |
| 277 | 39 # Dataflow fixed point iteration: |
| 337 | 40 n_iterations = 0 |
| 277 | 41 change = True |
| 42 while change: | |
| 43 change = False | |
| 337 | 44 for n in cfg_nodes: |
| 277 | 45 _in = n.live_in |
| 46 _out = n.live_out | |
| 47 n.live_in = n.uses | (n.live_out - n.defs) | |
| 48 if n.Succ: | |
| 49 n.live_out = set.union(*(s.live_in for s in n.Succ)) | |
| 50 else: | |
| 51 n.live_out = set() | |
| 313 | 52 n.live_out = n.live_out | n.defs |
| 277 | 53 change = change or (_in != n.live_in) or (_out != n.live_out) |
| 337 | 54 n_iterations += 1 |
| 277 | 55 |
| 337 | 56 self.logger.debug('Iterations: {} * {}'.format(n_iterations, len(cfg_nodes))) |
| 277 | 57 # Construct interference graph: |
| 58 for n in flowgraph.nodes: | |
| 59 for tmp in n.live_out: | |
| 60 n1 = self.getNode(tmp) | |
| 61 for tmp2 in (n.live_out - {tmp}): | |
| 62 n2 = self.getNode(tmp2) | |
| 63 self.addEdge(n1, n2) | |
| 64 | |
| 279 | 65 def to_dot(self, f): |
| 66 """ Generate graphviz dot representation """ | |
| 296 | 67 for n in self.nodes: |
| 314 | 68 print(' {} [label="{}" shape=box3d];'.format(id(n), n), file=f) |
| 279 | 69 for n, m in self.edges: |
| 314 | 70 print(' {} -> {};'.format(id(n), id(m)), file=f) |
| 279 | 71 |
| 72 def to_txt(self): | |
| 73 for node in self.nodes: | |
| 74 print('{} interferes: {}'.format(node, node.Adjecent)) | |
| 75 | |
| 277 | 76 def getNode(self, tmp): |
|
278
9fca39eebe50
First implementation of regalloc with coalsesc
Windel Bouwman
parents:
277
diff
changeset
|
77 # Linear search |
|
9fca39eebe50
First implementation of regalloc with coalsesc
Windel Bouwman
parents:
277
diff
changeset
|
78 # TODO: can be improved for speed! |
|
9fca39eebe50
First implementation of regalloc with coalsesc
Windel Bouwman
parents:
277
diff
changeset
|
79 for n in self.nodes: |
|
9fca39eebe50
First implementation of regalloc with coalsesc
Windel Bouwman
parents:
277
diff
changeset
|
80 if tmp in n.temps: |
|
9fca39eebe50
First implementation of regalloc with coalsesc
Windel Bouwman
parents:
277
diff
changeset
|
81 return n |
|
9fca39eebe50
First implementation of regalloc with coalsesc
Windel Bouwman
parents:
277
diff
changeset
|
82 n = InterferenceGraphNode(self, tmp) |
| 337 | 83 self.add_node(n) |
| 277 | 84 return n |
| 85 | |
|
278
9fca39eebe50
First implementation of regalloc with coalsesc
Windel Bouwman
parents:
277
diff
changeset
|
86 def Combine(self, n, m): |
|
9fca39eebe50
First implementation of regalloc with coalsesc
Windel Bouwman
parents:
277
diff
changeset
|
87 """ Combine n and m into n """ |
|
9fca39eebe50
First implementation of regalloc with coalsesc
Windel Bouwman
parents:
277
diff
changeset
|
88 n.temps.extend(m.temps) |
|
9fca39eebe50
First implementation of regalloc with coalsesc
Windel Bouwman
parents:
277
diff
changeset
|
89 n.moves.update(m.moves) |
| 279 | 90 # Reroute all edges: |
| 91 e1 = [e for e in self.edges if e[0] is m] | |
| 92 e2 = [e for e in self.edges if e[1] is m] | |
| 93 for e in e1: | |
| 94 self.edges.remove(e) | |
| 95 self.addEdge(n, e[1]) | |
| 96 for e in e2: | |
| 97 self.edges.remove(e) | |
| 98 self.addEdge(n, e[0]) | |
| 99 # Remove node m: | |
|
278
9fca39eebe50
First implementation of regalloc with coalsesc
Windel Bouwman
parents:
277
diff
changeset
|
100 self.delNode(m) |