Mercurial > lcfOS

comparison python/ppci/codegen/interferencegraph.py @ 337:b00219172a42

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added cool lm3s811 qemu project
author Windel Bouwman
date Thu, 20 Feb 2014 20:04:52 +0100
parents 38f5f298ce0e
children 39bf68bf1891
comparison
equal deleted inserted replaced
336:d1ecc493384e 337:b00219172a42
1 import logging
1 from .graph import Graph, Node 2 from .graph import Graph, Node
2 3
3 4
4 class InterferenceGraphNode(Node): 5 class InterferenceGraphNode(Node):
5 def __init__(self, g, varname): 6 def __init__(self, g, varname):
17 Interference graph. 18 Interference graph.
18 """ 19 """
19 def __init__(self, flowgraph): 20 def __init__(self, flowgraph):
20 """ Create a new interference graph from a flowgraph """ 21 """ Create a new interference graph from a flowgraph """
21 super().__init__() 22 super().__init__()
23 self.logger = logging.getLogger('interferencegraph')
22 # Calculate liveness in CFG: 24 # Calculate liveness in CFG:
23 ### 25 ###
24 # Liveness: 26 # Liveness:
25 # in[n] = use[n] UNION (out[n] - def[n]) 27 # in[n] = use[n] UNION (out[n] - def[n])
26 # out[n] = for s in n.succ in union in[s] 28 # out[n] = for s in n.succ in union in[s]
27 ### 29 ###
28 for n in flowgraph.nodes: 30 for n in flowgraph.nodes:
29 n.live_in = set() 31 n.live_in = set()
30 n.live_out = set() 32 n.live_out = set()
31 33
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
32 # Dataflow fixed point iteration: 39 # Dataflow fixed point iteration:
40 n_iterations = 0
33 change = True 41 change = True
34 while change: 42 while change:
35 change = False 43 change = False
36 for n in flowgraph.nodes: 44 for n in cfg_nodes:
37 _in = n.live_in 45 _in = n.live_in
38 _out = n.live_out 46 _out = n.live_out
39 n.live_in = n.uses | (n.live_out - n.defs) 47 n.live_in = n.uses | (n.live_out - n.defs)
40 if n.Succ: 48 if n.Succ:
41 n.live_out = set.union(*(s.live_in for s in n.Succ)) 49 n.live_out = set.union(*(s.live_in for s in n.Succ))
42 else: 50 else:
43 n.live_out = set() 51 n.live_out = set()
44 n.live_out = n.live_out | n.defs 52 n.live_out = n.live_out | n.defs
45 change = change or (_in != n.live_in) or (_out != n.live_out) 53 change = change or (_in != n.live_in) or (_out != n.live_out)
54 n_iterations += 1
46 55
56 self.logger.debug('Iterations: {} * {}'.format(n_iterations, len(cfg_nodes)))
47 # Construct interference graph: 57 # Construct interference graph:
48 for n in flowgraph.nodes: 58 for n in flowgraph.nodes:
49 for tmp in n.live_out: 59 for tmp in n.live_out:
50 n1 = self.getNode(tmp) 60 n1 = self.getNode(tmp)
51 for tmp2 in (n.live_out - {tmp}): 61 for tmp2 in (n.live_out - {tmp}):
68 # TODO: can be improved for speed! 78 # TODO: can be improved for speed!
69 for n in self.nodes: 79 for n in self.nodes:
70 if tmp in n.temps: 80 if tmp in n.temps:
71 return n 81 return n
72 n = InterferenceGraphNode(self, tmp) 82 n = InterferenceGraphNode(self, tmp)
73 self.addNode(n) 83 self.add_node(n)
74 return n 84 return n
75 85
76 def Combine(self, n, m): 86 def Combine(self, n, m):
77 """ Combine n and m into n """ 87 """ Combine n and m into n """
78 n.temps.extend(m.temps) 88 n.temps.extend(m.temps)