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