annotate python/ir.py @ 279:2ccd57b1d78c

Fix register allocator to do burn2 OK
author Windel Bouwman
date Sat, 12 Oct 2013 09:56:23 +0200
parents 046017431c6a
children 02385f62f250
rev   line source
277
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
1 """
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
2 Intermediate representation (IR) code classes.
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
3 """
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
4
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
5
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
6 def dumpgv(m, outf):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
7 print('digraph G ', file=outf)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
8 print('{', file=outf)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
9 for f in m.Functions:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
10 print('{} [label="{}" shape=box3d]'.format(id(f), f),file=outf)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
11 for bb in f.Blocks:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
12 contents = str(bb) + '\n'
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
13 contents += '\n'.join([str(i) for i in bb.Instructions])
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
14 outf.write('{0} [shape=note label="{1}"];\n'.format(id(bb), contents))
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
15 for successor in bb.Successors:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
16 print('"{}" -> "{}"\n'.format(id(bb), id(successor)), file=outf)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
17
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
18 outf.write('"{}" -> "{}" [label="entry"]\n'.format(id(f), id(f.entry)))
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
19 print('}', file=outf)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
20
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
21
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
22 class Module:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
23 """ Main container of variables and functions. """
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
24 def __init__(self, name):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
25 self.name = name
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
26 self.funcs = []
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
27 self.variables = []
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
28
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
29 def __repr__(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
30 return 'IR-module [{0}]'.format(self.name)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
31
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
32 def addFunc(self, f):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
33 self.funcs.append(f)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
34
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
35 addFunction = addFunc
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
36
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
37 def addVariable(self, v):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
38 self.variables.append(v)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
39
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
40 def getVariables(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
41 return self.variables
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
42
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
43 Variables = property(getVariables)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
44
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
45 def getFunctions(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
46 return self.funcs
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
47
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
48 Functions = property(getFunctions)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
49
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
50 def findFunction(self, name):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
51 for f in self.funcs:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
52 if f.name == name:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
53 return f
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
54 raise KeyError(name)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
55
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
56 getFunction = findFunction
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
57
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
58 def dump(self, indent=' '):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
59 print(self)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
60 for v in self.Variables:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
61 print(indent, v)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
62 for fn in self.Functions:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
63 fn.dump(indent=indent+' ')
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
64
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
65 # Analysis functions:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
66 def check(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
67 """ Perform sanity check on module """
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
68 for f in self.Functions:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
69 f.check()
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
70
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
71
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
72 class Function:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
73 """
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
74 Function definition. Contains an entry block.
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
75 """
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
76 def __init__(self, name):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
77 self.name = name
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
78 self.entry = Block('{}_entry'.format(name))
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
79 self.epiloog = Block('{}_epilog'.format(name))
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
80 self.epiloog.addInstruction(Terminator())
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
81 self.return_value = Temp('{}_retval'.format(name))
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
82 self.arguments = []
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
83 self.localvars = []
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
84
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
85 def __repr__(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
86 args = ','.join(str(a) for a in self.arguments)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
87 return 'Function {}({})'.format(self.name, args)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
88
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
89 def addBB(self, bb):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
90 self.bbs.append(bb)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
91 bb.parent = self
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
92 addBlock = addBB
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
93
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
94 def removeBasicBlock(self, bb):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
95 self.bbs.remove(bb)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
96 bb.parent = None
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
97
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
98 def getBBs(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
99 bbs = [self.entry]
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
100 worklist = [self.entry]
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
101 while worklist:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
102 b = worklist.pop()
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
103 for sb in b.Successors:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
104 if sb not in bbs:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
105 bbs.append(sb)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
106 worklist.append(sb)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
107 bbs.remove(self.entry)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
108 if self.epiloog in bbs:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
109 bbs.remove(self.epiloog)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
110 bbs.insert(0, self.entry)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
111 bbs.append(self.epiloog)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
112 return bbs
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
113
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
114 def findBasicBlock(self, name):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
115 for bb in self.bbs:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
116 if bb.name == name:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
117 return bb
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
118 raise KeyError(name)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
119
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
120 Blocks = property(getBBs)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
121
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
122 @property
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
123 def Entry(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
124 return self.entry
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
125
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
126 def check(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
127 for b in self.Blocks:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
128 b.check()
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
129
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
130 def addParameter(self, p):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
131 assert type(p) is Parameter
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
132 p.num = len(self.arguments)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
133 self.arguments.append(p)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
134
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
135 def addLocal(self, l):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
136 assert type(l) is LocalVariable
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
137 self.localvars.append(l)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
138
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
139 def dump(self, indent=''):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
140 print(indent+str(self))
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
141 for bb in self.Blocks:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
142 print(indent+' '+str(bb))
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
143 for ins in bb.Instructions:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
144 print(indent +' '*2 + str(ins))
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
145
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
146
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
147 class Block:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
148 """
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
149 Uninterrupted sequence of instructions with a label at the start.
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
150 """
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
151 def __init__(self, name):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
152 self.name = name
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
153 self.instructions = []
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
154
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
155 def __repr__(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
156 return 'Block {0}'.format(self.name)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
157
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
158 def addInstruction(self, i):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
159 i.parent = self
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
160 assert not isinstance(self.LastInstruction, LastStatement)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
161 self.instructions.append(i)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
162
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
163 def replaceInstruction(self, i1, i2):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
164 idx = self.instructions.index(i1)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
165 i1.parent = None
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
166 i1.delete()
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
167 i2.parent = self
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
168 self.instructions[idx] = i2
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
169
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
170 def removeInstruction(self, i):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
171 i.parent = None
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
172 i.delete()
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
173 self.instructions.remove(i)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
174
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
175 def getInstructions(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
176 return self.instructions
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
177 Instructions = property(getInstructions)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
178
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
179 def getLastIns(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
180 if not self.Empty:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
181 return self.instructions[-1]
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
182 LastInstruction = property(getLastIns)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
183
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
184 @property
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
185 def Empty(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
186 return len(self.instructions) == 0
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
187
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
188 @property
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
189 def FirstInstruction(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
190 return self.instructions[0]
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
191
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
192 def getSuccessors(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
193 if not self.Empty:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
194 return self.LastInstruction.Targets
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
195 return []
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
196 Successors = property(getSuccessors)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
197
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
198 def getPredecessors(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
199 preds = []
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
200 for bb in self.parent.BasicBlocks:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
201 if self in bb.Successors:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
202 preds.append(bb)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
203 return preds
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
204 Predecessors = property(getPredecessors)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
205
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
206 def precedes(self, other):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
207 raise NotImplementedError()
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
208
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
209 def check(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
210 assert isinstance(self.LastInstruction, LastStatement)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
211 for i in self.instructions[:-1]:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
212 assert not isinstance(i, LastStatement)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
213
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
214
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
215 # Instructions:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
216 class Term:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
217 def __init__(self, x):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
218 self.x = x
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
219
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
220 def match_tree(tree, pattern):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
221 if type(pattern) is Term:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
222 return True, {pattern: tree}
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
223 elif type(pattern) is Binop and type(tree) is Binop and tree.operation == pattern.operation:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
224 res_a, mp_a = match_tree(tree.a, pattern.a)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
225 res_b, mp_b = match_tree(tree.b, pattern.b)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
226 assert not (mp_a.keys() & mp_b.keys())
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
227 mp_a.update(mp_b)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
228 return res_a and res_b, mp_a
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
229 elif type(pattern) is Const and type(tree) is Const and pattern.value == tree.value:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
230 return True, {}
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
231 else:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
232 return False, {}
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
233
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
234
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
235 class Expression:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
236 pass
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
237
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
238
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
239 class Const(Expression):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
240 def __init__(self, value):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
241 self.value = value
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
242
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
243 def __repr__(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
244 return 'Const {}'.format(self.value)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
245
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
246
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
247 # Function calling:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
248 class Call(Expression):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
249 def __init__(self, f, arguments):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
250 self.f = f
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
251 assert type(f) is Function
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
252 self.arguments = arguments
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
253
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
254 def __repr__(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
255 args = ', '.join([str(arg) for arg in self.arguments])
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
256 return '{}({})'.format(self.f.name, args)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
257
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
258
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
259 # Data operations
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
260 class Binop(Expression):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
261 ops = ['+', '-', '*', '/', '|', '&', '<<', '>>']
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
262 def __init__(self, value1, operation, value2):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
263 assert operation in Binop.ops
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
264 self.a = value1
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
265 self.b = value2
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
266 self.operation = operation
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
267
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
268 def __repr__(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
269 a, b = self.a, self.b
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
270 return '({} {} {})'.format(a, self.operation, b)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
271
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
272
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
273 def Add(a, b):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
274 """ Convenience call """
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
275 return Binop(a, '+', b)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
276
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 277
diff changeset
277 def Sub(a, b):
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 277
diff changeset
278 return Binop(a, '-', b)
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 277
diff changeset
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 277
diff changeset
280 def Mul(a, b):
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 277
diff changeset
281 return Binop(a, '*', b)
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 277
diff changeset
282
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 277
diff changeset
283 def Div(a, b):
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 277
diff changeset
284 return Binop(a, '/', b)
277
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
285
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
286 class Eseq(Expression):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
287 """ Sequence of instructions where the last is an expression """
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
288 def __init__(self, stmt, e):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
289 self.stmt = stmt
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
290 self.e = e
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
291
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
292 def __repr__(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
293 return '({}, {})'.format(self.stmt, self.e)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
294
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
295
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
296 class Alloc(Expression):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
297 """ Allocates space on the stack """
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
298 def __init__(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
299 super().__init__()
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
300
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
301 def __repr__(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
302 return 'Alloc'
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
303
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
304
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
305 class Variable(Expression):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
306 def __init__(self, name):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
307 self.name = name
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
308
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
309 def __repr__(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
310 return 'Var {}'.format(self.name)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
311
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
312
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
313 class LocalVariable(Variable):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
314 def __repr__(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
315 return 'Local {}'.format(self.name)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
316
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
317
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
318 class Parameter(Variable):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
319 def __repr__(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
320 return 'Param {}'.format(self.name)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
321
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
322
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
323 class Temp(Expression):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
324 """ Temporary storage, same as register """
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
325 def __init__(self, name):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
326 self.name = name
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
327
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
328 def __repr__(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
329 return 'TMP_{}'.format(self.name)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
330
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
331
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
332 class Mem(Expression):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
333 def __init__(self, e):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
334 self.e = e
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
335
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
336 def __repr__(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
337 return '[{}]'.format(self.e)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
338
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
339
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
340 class Statement:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
341 """ Base class for all instructions. """
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
342 pass
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
343
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
344
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
345 class Move(Statement):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
346 def __init__(self, dst, src):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
347 self.dst = dst
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
348 self.src = src
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
349
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
350 def __repr__(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
351 return '{} = {}'.format(self.dst, self.src)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
352
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
353
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
354 class Exp(Statement):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
355 def __init__(self, e):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
356 self.e = e
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
357
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
358 def __repr__(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
359 return '{}'.format(self.e)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
360
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
361
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
362 class Label(Statement):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
363 # TODO: is this duplicate with block?
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
364 def __init__(self, name):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
365 self.name = name
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
366 self.statements = []
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
367
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
368 def __repr__(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
369 return 'LABEL {}:'.format(self.name)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
370
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
371
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
372 # Branching:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
373 class LastStatement(Statement):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
374 pass
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
375
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
376
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
377 class Terminator(LastStatement):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
378 """ Instruction that terminates the terminal block """
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
379 Targets = []
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
380 def __repr__(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
381 return 'Terminator'
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
382
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
383
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
384 class Jump(LastStatement):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
385 def __init__(self, target):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
386 self.target = target
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
387 self.Targets = [target]
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
388
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
389 def __repr__(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
390 return 'BRANCH {}'.format(self.target.name)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
391
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
392
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
393 class CJump(LastStatement):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
394 conditions = ['==', '<', '>', '>=', '<=', '!=']
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
395 def __init__(self, a, cond, b, lab_yes, lab_no):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
396 assert cond in CJump.conditions
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
397 self.a = a
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
398 self.cond = cond
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
399 self.b = b
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
400 self.lab_yes = lab_yes
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
401 self.lab_no = lab_no
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
402 self.Targets = [lab_yes, lab_no]
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
403
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
404 def __repr__(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
405 return 'IF {} {} {} THEN {} ELSE {}'.format(self.a, self.cond, self.b, self.lab_yes, self.lab_no)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
406
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
407
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 277
diff changeset
408 # Constructing IR:
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 277
diff changeset
409
277
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
410 class NamedClassGenerator:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
411 def __init__(self, prefix, cls):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
412 self.prefix = prefix
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
413 self.cls = cls
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
414 def NumGen():
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
415 a = 0
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
416 while True:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
417 yield a
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
418 a = a + 1
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
419 self.nums = NumGen()
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
420
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
421 def gen(self, prefix=None):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
422 if not prefix:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
423 prefix = self.prefix
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
424 return self.cls('{0}{1}'.format(prefix, self.nums.__next__()))
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
425
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
426
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
427 class Builder:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
428 """ Base class for ir code generators """
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
429 def __init__(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
430 self.prepare()
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
431
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
432 def prepare(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
433 self.newTemp = NamedClassGenerator('reg', Temp).gen
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
434 self.newBlock = NamedClassGenerator('block', Block).gen
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
435 self.bb = None
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
436 self.m = None
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
437 self.fn = None
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
438 self.loc = None
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
439
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
440 # Helpers:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
441 def setModule(self, m):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
442 self.m = m
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
443
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
444 def newFunction(self, name):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
445 f = Function(name)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
446 self.m.addFunc(f)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
447 return f
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
448
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
449 def setFunction(self, f):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
450 self.fn = f
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
451 self.bb = f.entry if f else None
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
452
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
453 def setBlock(self, b):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
454 self.bb = b
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
455
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
456 def setLoc(self, l):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
457 self.loc = l
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
458
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
459 def emit(self, i):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
460 assert isinstance(i, Statement)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
461 i.debugLoc = self.loc
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
462 if not self.bb:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
463 raise Exception('No basic block')
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
464 self.bb.addInstruction(i)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
465
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
466