|
157
|
1 # IR-Structures:
|
|
171
|
2 from .instruction import *
|
|
|
3 from .basicblock import BasicBlock
|
|
157
|
4
|
|
155
|
5 class Module:
|
|
170
|
6 """ Main container for a piece of code. """
|
|
155
|
7 def __init__(self, name):
|
|
|
8 self.name = name
|
|
171
|
9 self.bbs = []
|
|
158
|
10 def __repr__(self):
|
|
170
|
11 return 'IR-module [{0}]'.format(self.name)
|
|
155
|
12 def getInstructions(self):
|
|
171
|
13 ins = []
|
|
|
14 for bb in self.bbs:
|
|
|
15 ins += bb.Instructions
|
|
|
16 return ins
|
|
155
|
17 Instructions = property(getInstructions)
|
|
171
|
18 def addBB(self, bb):
|
|
|
19 self.bbs.append(bb)
|
|
|
20 def getBBs(self):
|
|
|
21 return self.bbs
|
|
|
22 BasicBlocks = property(getBBs)
|
|
170
|
23 def dump(self):
|
|
|
24 print(self)
|
|
|
25 for i in self.Instructions:
|
|
171
|
26 print(i, 'live vars:', list(i.live_in), 'uses', list(i.uses), 'defs', list(i.defs))
|
|
170
|
27 print('END')
|
|
171
|
28 def dumpgv(self, outf):
|
|
|
29 outf.write('digraph G \n{\n')
|
|
|
30 for i in self.Instructions:
|
|
|
31 outf.write('{0} [label="{1}"];\n'.format(id(i), i))
|
|
|
32 for succ in i.succ:
|
|
|
33 outf.write('"{0}" -> "{1}" [label="{2}"];\n'.format(id(i), id(succ), succ.live_in))
|
|
|
34 outf.write('}\n')
|
|
155
|
35
|
|
171
|
36 # Analysis functions:
|
|
|
37 def check(self):
|
|
|
38 """ Perform sanity check on module """
|
|
|
39 for i in self.Instructions:
|
|
|
40 for t in i.defs:
|
|
|
41 assert type(t) is Value, "def must be Value, not {0}".format(type(t))
|
|
|
42 for t in i.uses:
|
|
|
43 assert type(t) is Value, "use must be Value, not {0}".format(type(t))
|
|
|
44 def analyze(self):
|
|
|
45 # Determine pred and succ:
|
|
|
46 def link(a, b):
|
|
|
47 a.succ.add(b)
|
|
|
48 b.pred.add(a)
|
|
|
49 for bb in self.bbs:
|
|
|
50 if not bb.Empty:
|
|
|
51 if len(bb.Instructions) > 1:
|
|
|
52 for i1, i2 in zip(bb.Instructions[:-1], bb.Instructions[1:]):
|
|
|
53 link(i1, i2)
|
|
|
54 else:
|
|
|
55 print('Only 1 long!', bb, bb.Instructions)
|
|
|
56 if type(bb.LastIns) is ConditionalBranch:
|
|
|
57 link(bb.LastIns, bb.LastIns.lab1.FirstIns)
|
|
|
58 link(bb.LastIns, bb.LastIns.lab2.FirstIns)
|
|
|
59 if type(bb.LastIns) is Branch:
|
|
|
60 link(bb.LastIns, bb.LastIns.target.FirstIns)
|
|
|
61 else:
|
|
|
62 print('Empty!', bb)
|
|
|
63 # We now have cfg
|
|
|
64
|
|
|
65 # Determine liveness:
|
|
|
66 for i in self.Instructions:
|
|
|
67 i.live_in = set()
|
|
|
68 i.live_out = set()
|
|
|
69 for z in range(50):
|
|
|
70 # TODO iterate until converge
|
|
|
71 for i in self.Instructions:
|
|
|
72 lo_mk = i.live_out.difference(i.defs)
|
|
|
73 i.live_in = i.uses.union(lo_mk)
|
|
|
74 lo = set()
|
|
|
75 for s in i.succ:
|
|
|
76 lo = lo.union(s.live_in)
|
|
|
77 i.live_out = lo
|
|
|
78 def constantProp(self):
|
|
|
79 """ Constant propagation. Pre-calculate constant values """
|
|
|
80 for i in self.Instructions:
|
|
|
81 if type(i) is ImmLoad:
|
|
|
82 i.target.constval = i.value
|
|
|
83 elif type(i) is BinaryOperator:
|
|
|
84 a = i.value1
|
|
|
85 b = i.value2
|
|
|
86 if i.value1.constval and i.value2.constval:
|
|
|
87 op = i.operation
|
|
|
88 if op == '+':
|
|
|
89 i.result.constval = a + b
|
|
|
90 else:
|
|
|
91 raise NotImplementedError(op)
|
|
|
92 else:
|
|
|
93 i.result.constval = None
|
|
|
94
|
|
|
95 def registerAllocate(self, regs):
|
|
|
96 print(regs)
|
|
|
97 allVals = []
|
|
|
98 # construct interference:
|
|
|
99 for i in self.Instructions:
|
|
|
100 for v in i.live_in:
|
|
|
101 allVals.append(v)
|
|
|
102 for v2 in i.live_in:
|
|
|
103 if v != v2:
|
|
|
104 v.interferes.add(v2)
|
|
|
105 # assign random registers:
|
|
|
106 print(allVals)
|
|
|
107 regs = set(regs)
|
|
|
108 for v in allVals:
|
|
|
109 takenregs = set([iv.reg for iv in v.interferes])
|
|
|
110 r2 = list(regs.difference(takenregs))
|
|
|
111 # Pick next available:
|
|
|
112 v.reg = r2[0]
|
|
|
113
|
