Mercurial > lcfOS

comparison python/registerallocator.py @ 269:5f8c04a8d26b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Towards better modularity
author Windel Bouwman
date Sun, 18 Aug 2013 17:43:18 +0200
parents a51b3c956386
children cdc76d183bcc
comparison
equal deleted inserted replaced
268:5ec7580976d9 269:5f8c04a8d26b
1
2 import graph
3
4 class InterferenceGraphNode(graph.Node):
5 def __init__(self, g, varname):
6 super().__init__(g)
7 self.varname = varname
8
9 def __repr__(self):
10 return '{}'.format(self.varname)
11
12
13 class InterferenceGraph(graph.Graph):
14 def __init__(self, flowgraph):
15 """ Create a new interference graph from a flowgraph """
16 super().__init__()
17 # Mapping from node to live set
18 self.liveMap = {}
19 self.tempMap = {}
20 # Calculate liveness in CFG:
21 ###
22 # Liveness:
23 # in[n] = use[n] UNION (out[n] - def[n])
24 # out[n] = for s in n.succ in union in[s]
25 ###
26 for n in flowgraph.nodes:
27 n.live_in = set()
28 n.live_out = set()
29 # Dataflow fixed point iteration:
30 change = True
31 while change:
32 change = False
33 for n in flowgraph.nodes:
34 _in = n.live_in
35 _out = n.live_out
36 n.live_in = n.uses | (n.live_out - n.defs)
37 if n.succ:
38 n.live_out = set.union(*(s.live_in for s in n.succ))
39 else:
40 n.live_out = set()
41 change = change or (_in != n.live_in) or (_out != n.live_out)
42 # Construct interference graph:
43 for n in flowgraph.nodes:
44 for tmp in n.live_out:
45 n1 = self.getNode(tmp)
46 for tmp2 in (n.live_out - {tmp}):
47 n2 = self.getNode(tmp2)
48 self.addEdge(n1, n2)
49
50 def getNode(self, tmp):
51 if tmp not in self.tempMap:
52 self.tempMap[tmp] = self.newNode(tmp)
53 return self.tempMap[tmp]
54
55 def newNode(self, varname):
56 n = InterferenceGraphNode(self, varname)
57 self.nodes.append(n)
58 return n
59
1 60
2 class RegisterAllocator: 61 class RegisterAllocator:
3 def live_analyze(self): 62 """ Target independent register allocator """
4 # Determine liveness: 63 def registerAllocate(self, ig, regs):
5 for i in self.Instructions: 64 """ Color the given interference graph with the provided registers """
6 i.live_in = set() 65 self.regMap = {}
7 i.live_out = set() 66 # TODO: implement ;)
8 for z in range(50): 67 regs = set(regs)
9 # TODO iterate until converge 68 for n in ig.nodes:
10 for i in self.Instructions: 69 print(n)
11 lo_mk = i.live_out.difference(i.defs)
12 i.live_in = i.uses.union(lo_mk)
13 lo = set()
14 for s in i.succ:
15 lo = lo.union(s.live_in)
16 i.live_out = lo
17 def registerAllocate(self, ir, regs):
18 allVals = []
19 # construct interference:
20 for i in ir.Instructions:
21 for v in i.live_in:
22 allVals.append(v)
23 for v2 in i.live_in:
24 if v != v2:
25 v.interferes.add(v2)
26 # assign random registers:
27 regs = set(regs)
28 for v in allVals:
29 takenregs = set([iv.reg for iv in v.interferes])
30 r2 = list(regs.difference(takenregs))
31 # Pick next available:
32 v.reg = r2[0]
33 70
71 # TODO: implement spilling
72 # TODO: implement coalescing
73