|
307
|
1
|
|
|
2 """
|
|
|
3 Some utilities for ir-code.
|
|
|
4 """
|
|
309
|
5 import re
|
|
|
6 from . import ir
|
|
307
|
7
|
|
|
8 def dumpgv(m, outf):
|
|
|
9 print('digraph G ', file=outf)
|
|
|
10 print('{', file=outf)
|
|
|
11 for f in m.Functions:
|
|
|
12 print('{} [label="{}" shape=box3d]'.format(id(f), f), file=outf)
|
|
|
13 for bb in f.Blocks:
|
|
|
14 contents = str(bb) + '\n'
|
|
|
15 contents += '\n'.join([str(i) for i in bb.Instructions])
|
|
|
16 print('{0} [shape=note label="{1}"];'
|
|
|
17 .format(id(bb), contents), file=outf)
|
|
|
18 for successor in bb.Successors:
|
|
|
19 print('"{}" -> "{}"'.format(id(bb), id(successor)), file=outf)
|
|
|
20
|
|
|
21 print('"{}" -> "{}" [label="entry"]'
|
|
|
22 .format(id(f), id(f.entry)), file=outf)
|
|
|
23 print('}', file=outf)
|
|
|
24
|
|
|
25
|
|
309
|
26 class Writer:
|
|
312
|
27 def __init__(self, extra_indent=''):
|
|
|
28 self.extra_indent = extra_indent
|
|
|
29
|
|
309
|
30 def write(self, ir, f):
|
|
|
31 """ Write ir-code to file f """
|
|
312
|
32 print('{}{}'.format(self.extra_indent, ir), file=f)
|
|
309
|
33 for v in ir.Variables:
|
|
312
|
34 print('{}{}'.format(self.extra_indent, v), file=f)
|
|
|
35 for function in ir.Functions:
|
|
|
36 self.write_function(function, f)
|
|
|
37
|
|
|
38 def write_function(self, fn, f):
|
|
|
39 args = ','.join('i32 ' + str(a) for a in fn.arguments)
|
|
|
40 print('{}function i32 {}({})'.format(self.extra_indent, fn.name, args), file=f)
|
|
|
41 for bb in fn.Blocks:
|
|
|
42 print('{} {}'.format(self.extra_indent, bb), file=f)
|
|
|
43 for ins in bb.Instructions:
|
|
|
44 print('{} {}'.format(self.extra_indent, ins), file=f)
|
|
309
|
45
|
|
|
46
|
|
|
47 class IrParseException(Exception):
|
|
|
48 pass
|
|
|
49
|
|
|
50
|
|
|
51 class Reader:
|
|
|
52 def read(self, f):
|
|
|
53 """ Read ir code from file f """
|
|
|
54 # Read lines from the file:
|
|
|
55 lines = [line.rstrip() for line in f]
|
|
|
56
|
|
|
57 # Create a regular expression for the lexing part:
|
|
|
58 tok_spec = [
|
|
|
59 ('NUMBER', r'\d+'),
|
|
|
60 ('ID', r'[A-Za-z][A-Za-z\d_]*'),
|
|
|
61 ('SKIP2', r' '),
|
|
|
62 ('SKIP1', r' '),
|
|
|
63 ('OTHER', r'[\.,=:;\-+*\[\]/\(\)]|>|<|{|}|&|\^|\|')
|
|
|
64 ]
|
|
|
65 tok_re = '|'.join('(?P<%s>%s)' % pair for pair in tok_spec)
|
|
|
66 gettok = re.compile(tok_re).match
|
|
|
67
|
|
|
68 def tokenize():
|
|
|
69 for line in lines:
|
|
|
70 if not line:
|
|
|
71 continue # Skip empty lines
|
|
|
72 mo = gettok(line)
|
|
|
73 first = True
|
|
|
74 while mo:
|
|
|
75 typ = mo.lastgroup
|
|
|
76 val = mo.group(typ)
|
|
|
77 if typ == 'ID':
|
|
|
78 if val in ['function', 'module']:
|
|
|
79 typ = val
|
|
|
80 yield (typ, val)
|
|
|
81 elif typ == 'OTHER':
|
|
|
82 typ = val
|
|
|
83 yield (typ, val)
|
|
|
84 elif typ in ['SKIP1', 'SKIP2']:
|
|
|
85 if first:
|
|
|
86 yield (typ, val)
|
|
|
87 elif typ == 'NUMBER':
|
|
|
88 yield (typ, int(val))
|
|
|
89 else:
|
|
|
90 raise NotImplementedError(str(typ))
|
|
|
91 first = False
|
|
|
92 pos = mo.end()
|
|
|
93 mo = gettok(line, pos)
|
|
|
94 if len(line) != pos:
|
|
|
95 raise IrParseException('Lex fault')
|
|
|
96 yield ('eol', 'eol')
|
|
|
97 yield ('eof', 'eof')
|
|
|
98 self.tokens = tokenize()
|
|
|
99 self.token = self.tokens.__next__()
|
|
|
100
|
|
|
101 try:
|
|
|
102 module = self.parse_module()
|
|
|
103 return module
|
|
|
104 except IrParseException as e:
|
|
|
105 print(e)
|
|
|
106
|
|
|
107 def next_token(self):
|
|
|
108 t = self.token
|
|
|
109 if t[0] != 'eof':
|
|
|
110 self.token = self.tokens.__next__()
|
|
|
111 return t
|
|
|
112
|
|
|
113 @property
|
|
|
114 def Peak(self):
|
|
|
115 return self.token[0]
|
|
|
116
|
|
|
117 def Consume(self, typ):
|
|
|
118 if self.Peak == typ:
|
|
|
119 return self.next_token()
|
|
|
120 else:
|
|
|
121 raise IrParseException('Expected "{}" got "{}"'.format(typ, self.Peak))
|
|
318
|
122
|
|
309
|
123 def parse_module(self):
|
|
|
124 """ Entry for recursive descent parser """
|
|
|
125 self.Consume('module')
|
|
|
126 name = self.Consume('ID')[1]
|
|
|
127 module = ir.Module(name)
|
|
|
128 self.Consume('eol')
|
|
|
129 while self.Peak != 'eof':
|
|
|
130 if self.Peak == 'function':
|
|
|
131 module.add_function(self.parse_function())
|
|
|
132 else:
|
|
|
133 raise IrParseException('Expected function got {}'.format(self.Peak))
|
|
|
134 return module
|
|
318
|
135
|
|
309
|
136 def parse_function(self):
|
|
|
137 self.Consume('function')
|
|
|
138 self.parse_type()
|
|
|
139 name = self.Consume('ID')[1]
|
|
|
140 function = ir.Function(name)
|
|
|
141 self.Consume('(')
|
|
|
142 while self.Peak != ')':
|
|
|
143 self.parse_type()
|
|
|
144 self.Consume('ID')
|
|
|
145 if self.Peak != ',':
|
|
|
146 break
|
|
|
147 else:
|
|
|
148 self.Consume(',')
|
|
|
149 self.Consume(')')
|
|
|
150 self.Consume('eol')
|
|
|
151 while self.Peak == 'SKIP1':
|
|
|
152 function.add_block(self.parse_block())
|
|
|
153 return function
|
|
|
154
|
|
|
155 def parse_type(self):
|
|
|
156 self.Consume('ID')
|
|
|
157
|
|
|
158 def parse_block(self):
|
|
|
159 self.Consume('SKIP1')
|
|
|
160 name = self.Consume('ID')[1]
|
|
|
161 block = ir.Block(name)
|
|
|
162 self.Consume(':')
|
|
|
163 self.Consume('eol')
|
|
|
164 while self.Peak == 'SKIP2':
|
|
|
165 self.parse_statement()
|
|
|
166 return block
|
|
|
167
|
|
|
168 def parse_statement(self):
|
|
|
169 self.Consume('SKIP2')
|
|
|
170 while self.Peak != 'eol':
|
|
|
171 # raise NotImplementedError()
|
|
|
172 self.next_token()
|
|
|
173 self.Consume('eol')
|
|
|
174
|
|
|
175
|
|
307
|
176 # Constructing IR:
|
|
|
177
|
|
|
178 class NamedClassGenerator:
|
|
|
179 def __init__(self, prefix, cls):
|
|
|
180 self.prefix = prefix
|
|
|
181 self.cls = cls
|
|
|
182
|
|
|
183 def NumGen():
|
|
|
184 a = 0
|
|
|
185 while True:
|
|
|
186 yield a
|
|
|
187 a = a + 1
|
|
|
188 self.nums = NumGen()
|
|
|
189
|
|
|
190 def gen(self, prefix=None):
|
|
|
191 if not prefix:
|
|
|
192 prefix = self.prefix
|
|
|
193 return self.cls('{0}{1}'.format(prefix, self.nums.__next__()))
|
|
|
194
|
|
|
195
|
|
|
196 class Builder:
|
|
|
197 """ Base class for ir code generators """
|
|
|
198 def __init__(self):
|
|
|
199 self.prepare()
|
|
|
200
|
|
|
201 def prepare(self):
|
|
312
|
202 self.newTemp = NamedClassGenerator('reg', ir.Temp).gen
|
|
|
203 self.newBlock2 = NamedClassGenerator('block', ir.Block).gen
|
|
307
|
204 self.bb = None
|
|
|
205 self.m = None
|
|
|
206 self.fn = None
|
|
|
207 self.loc = None
|
|
|
208
|
|
|
209 # Helpers:
|
|
|
210 def setModule(self, m):
|
|
|
211 self.m = m
|
|
|
212
|
|
|
213 def newFunction(self, name):
|
|
312
|
214 f = ir.Function(name)
|
|
309
|
215 self.m.add_function(f)
|
|
307
|
216 return f
|
|
|
217
|
|
|
218 def newBlock(self):
|
|
|
219 assert self.fn
|
|
|
220 b = self.newBlock2()
|
|
|
221 b.function = self.fn
|
|
|
222 return b
|
|
|
223
|
|
|
224 def setFunction(self, f):
|
|
|
225 self.fn = f
|
|
|
226 self.bb = f.entry if f else None
|
|
|
227
|
|
|
228 def setBlock(self, b):
|
|
|
229 self.bb = b
|
|
|
230
|
|
|
231 def setLoc(self, l):
|
|
|
232 self.loc = l
|
|
|
233
|
|
|
234 def emit(self, i):
|
|
312
|
235 assert isinstance(i, ir.Statement)
|
|
307
|
236 i.debugLoc = self.loc
|
|
|
237 if not self.bb:
|
|
|
238 raise Exception('No basic block')
|
|
|
239 self.bb.addInstruction(i)
|
|
312
|
240
|
|
|
241
|
|
|
242 class Verifier:
|
|
|
243 def verify(self, module):
|
|
|
244 """ Verifies a module for some sanity """
|
|
|
245 assert isinstance(module, ir.Module)
|
|
|
246 for f in module.Functions:
|
|
|
247 self.verify_function(f)
|
|
|
248
|
|
|
249 def verify_function(self, function):
|
|
|
250 for b in function.Blocks:
|
|
|
251 self.verify_block_termination(b)
|
|
|
252
|
|
|
253 # Now we can build a dominator tree
|
|
|
254 for b in function.Blocks:
|
|
|
255 self.verify_block(b)
|
|
|
256
|
|
|
257 def verify_block_termination(self, block):
|
|
|
258 assert not block.Empty
|
|
|
259 assert block.LastInstruction.IsTerminator
|
|
317
|
260 for i in block.Instructions[:-1]:
|
|
|
261 assert not isinstance(i, ir.LastStatement)
|
|
318
|
262
|
|
312
|
263 def verify_block(self, block):
|
|
|
264 for instruction in block.Instructions:
|
|
|
265 self.verify_instruction(instruction)
|
|
|
266
|
|
|
267 def verify_instruction(self, instruction):
|
|
|
268 pass
|
