|
173
|
1
|
|
|
2 class RegisterAllocator:
|
|
|
3 def live_analyze(self):
|
|
|
4 # Determine liveness:
|
|
|
5 for i in self.Instructions:
|
|
|
6 i.live_in = set()
|
|
|
7 i.live_out = set()
|
|
|
8 for z in range(50):
|
|
|
9 # TODO iterate until converge
|
|
|
10 for i in self.Instructions:
|
|
|
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
|
