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