|
171
|
1 from .basicblock import BasicBlock
|
|
175
|
2 from .function import Function
|
|
171
|
3
|
|
205
|
4
|
|
171
|
5 class Value:
|
|
230
|
6 """ Temporary SSA value (value that is assigned only once! """
|
|
|
7 def __init__(self, name):
|
|
239
|
8 # TODO: add typing? for now only handle integers
|
|
|
9 self.name = name
|
|
|
10 self.used_by = []
|
|
|
11 self.Setter = None
|
|
230
|
12
|
|
|
13 def __repr__(self):
|
|
|
14 return '{0}'.format(self.name) # + str(self.IsUsed)
|
|
|
15
|
|
|
16 @property
|
|
252
|
17 def UsedInBlocks(self):
|
|
|
18 bbs = [i.parent for i in self.used_by + [self.Setter]]
|
|
|
19 assert all(isinstance(bb, BasicBlock) for bb in bbs)
|
|
|
20 return set(bbs)
|
|
|
21
|
|
|
22 @property
|
|
230
|
23 def IsUsed(self):
|
|
239
|
24 return len(self.used_by) > 0
|
|
|
25
|
|
252
|
26 Used = IsUsed
|
|
|
27
|
|
239
|
28 def onlyUsedInBlock(self, bb):
|
|
259
|
29 return all(use.Block is bb for use in self.used_by)
|
|
239
|
30
|
|
258
|
31 def lastUse(self, ins):
|
|
|
32 assert ins in self.used_by
|
|
|
33 return all(not ins.precedes(ub) for ub in self.used_by)
|
|
174
|
34
|
|
261
|
35 def replaceby(self, v2):
|
|
|
36 for use_ins in self.used_by:
|
|
|
37 use_ins.replaceValue(self, v2.value)
|
|
|
38 assert not self.Used
|
|
|
39
|
|
262
|
40
|
|
205
|
41 class Variable(Value):
|
|
|
42 pass
|
|
|
43
|
|
239
|
44
|
|
174
|
45 class Use:
|
|
239
|
46 def __init__(self, user, val):
|
|
|
47 self.user = user
|
|
|
48 assert isinstance(val, Value)
|
|
|
49 self.val = val
|
|
|
50 self.val.used_by.append(self.user)
|
|
|
51
|
|
|
52 def delete(self):
|
|
|
53 self.val.used_by.remove(self.user)
|
|
|
54
|
|
110
|
55
|
|
155
|
56 class Instruction:
|
|
239
|
57 """ Base class for all instructions. """
|
|
|
58 def __init__(self):
|
|
|
59 # live variables at this node:
|
|
|
60 self.live_in = set()
|
|
|
61 self.live_out = set()
|
|
|
62 # What variables this instruction uses and defines:
|
|
|
63 self.defs = []
|
|
|
64 self.uses = []
|
|
259
|
65
|
|
239
|
66 def delete(self):
|
|
209
|
67 while self.uses:
|
|
|
68 use = self.uses.pop()
|
|
|
69 use.delete()
|
|
239
|
70 while self.defs:
|
|
|
71 d = self.defs.pop()
|
|
|
72 d.Setter = None
|
|
|
73
|
|
|
74 def addUse(self, val):
|
|
|
75 self.uses.append(Use(self, val))
|
|
|
76
|
|
|
77 def removeUse(self, val):
|
|
|
78 for u in self.uses:
|
|
|
79 if u.val is val:
|
|
|
80 theUse = u
|
|
|
81 theUse.delete()
|
|
|
82 self.uses.remove(theUse)
|
|
|
83
|
|
|
84 def addDef(self, v):
|
|
|
85 self.defs.append(v)
|
|
|
86 assert v.Setter == None
|
|
|
87 v.Setter = self
|
|
|
88
|
|
|
89 def removeDef(self, v):
|
|
|
90 assert v.Setter is self
|
|
|
91 v.Setter = None
|
|
|
92 self.defs.remove(v)
|
|
|
93
|
|
|
94 def getParent(self):
|
|
|
95 return self.parent
|
|
|
96
|
|
|
97 def setParent(self, p):
|
|
|
98 self.parent = p
|
|
|
99 Parent = property(getParent, setParent)
|
|
|
100
|
|
|
101 def replaceValue(self, old, new):
|
|
262
|
102 # TODO: make this a generic function
|
|
252
|
103 raise NotImplementedError('{}'.format(type(self)))
|
|
239
|
104
|
|
|
105 @property
|
|
|
106 def Position(self):
|
|
258
|
107 return self.Block.Instructions.index(self)
|
|
|
108
|
|
|
109 def precedes(self, other):
|
|
|
110 assert isinstance(other, Instruction)
|
|
|
111 if self.Block is other.Block:
|
|
|
112 return other.Position > self.Position
|
|
259
|
113 else:
|
|
|
114 return self.Block.precedes(other.Block)
|
|
|
115
|
|
|
116 def follows(self, other):
|
|
|
117 pass
|
|
239
|
118
|
|
252
|
119 @property
|
|
|
120 def Function(self):
|
|
|
121 return self.Block.parent
|
|
|
122
|
|
|
123 @property
|
|
|
124 def Block(self):
|
|
|
125 return self.Parent
|
|
|
126
|
|
239
|
127 def check(self):
|
|
|
128 # Check that the variables defined by this instruction
|
|
|
129 # are only used in the same block
|
|
|
130 for v in self.defs:
|
|
|
131 assert v.Setter is self
|
|
|
132 for ub in v.used_by:
|
|
252
|
133 assert ub.Function == self.Function
|
|
239
|
134
|
|
|
135 # Check that variables used are defined earlier:
|
|
|
136 for u in self.uses:
|
|
|
137 v = u.val
|
|
252
|
138 #assert self.Position > v.Setter.Position
|
|
239
|
139
|
|
|
140
|
|
|
141
|
|
177
|
142
|
|
239
|
143
|
|
170
|
144
|
|
158
|
145 # Function calling:
|
|
171
|
146 class Call(Instruction):
|
|
175
|
147 def __init__(self, callee, arguments, result=None):
|
|
110
|
148 super().__init__()
|
|
|
149 self.callee = callee
|
|
175
|
150 assert type(callee) is Function
|
|
110
|
151 self.arguments = arguments
|
|
175
|
152 for arg in arguments:
|
|
|
153 assert type(arg) is Value
|
|
|
154 self.addUse(arg)
|
|
|
155 self.result = result
|
|
|
156 if result:
|
|
|
157 assert type(result) is Value
|
|
|
158 self.addDef(result)
|
|
261
|
159
|
|
158
|
160 def __repr__(self):
|
|
175
|
161 if self.result:
|
|
|
162 pfx = '{0} = '.format(self.result)
|
|
|
163 else:
|
|
|
164 pfx = ''
|
|
|
165 args = ','.join([str(arg) for arg in self.arguments])
|
|
|
166 return pfx + '{0}({1})'.format(self.callee.name, args)
|
|
110
|
167
|
|
70
|
168
|
|
174
|
169 class Alloc(Instruction):
|
|
261
|
170 """ Allocates space on the stack """
|
|
|
171 def __init__(self, value):
|
|
|
172 super().__init__()
|
|
|
173 assert isinstance(value, Value)
|
|
|
174 self.value = value
|
|
|
175 self.addDef(value)
|
|
|
176
|
|
|
177 def __repr__(self):
|
|
|
178 return '{0} = alloc'.format(self.value)
|
|
|
179
|
|
174
|
180
|
|
171
|
181 class ImmLoad(Instruction):
|
|
261
|
182 def __init__(self, target, value):
|
|
|
183 super().__init__()
|
|
|
184 assert type(target) is Value
|
|
|
185 self.target = target
|
|
|
186 self.value = value
|
|
|
187 self.addDef(target)
|
|
|
188
|
|
|
189 def __repr__(self):
|
|
|
190 return '{} = {}'.format(self.target, self.value)
|
|
170
|
191
|
|
262
|
192
|
|
171
|
193 # Data operations
|
|
70
|
194 class BinaryOperator(Instruction):
|
|
230
|
195 def __init__(self, result, operation, value1, value2):
|
|
261
|
196 super().__init__()
|
|
|
197 assert type(value1) is Value, str(value1) + str(type(value1))
|
|
|
198 assert type(value2) is Value, value2
|
|
|
199 self.result = result
|
|
|
200 self.addDef(result)
|
|
|
201 self.value1 = value1
|
|
|
202 self.value2 = value2
|
|
|
203 self.addUse(value1)
|
|
|
204 self.addUse(value2)
|
|
|
205 self.operation = operation
|
|
239
|
206
|
|
230
|
207 def __repr__(self):
|
|
|
208 a, b = self.value1, self.value2
|
|
|
209 return '{} = {} {} {}'.format(self.result, a, self.operation, b)
|
|
70
|
210
|
|
239
|
211 def replaceValue(self, old, new):
|
|
|
212 if old is self.value1:
|
|
|
213 self.value1 = new
|
|
|
214 elif old is self.value2:
|
|
|
215 self.value2 = new
|
|
|
216 elif old is self.result:
|
|
|
217 self.result = new
|
|
|
218 else:
|
|
|
219 raise Exception()
|
|
|
220 self.removeUse(old)
|
|
|
221 self.addUse(new)
|
|
|
222
|
|
261
|
223
|
|
170
|
224 # Memory functions:
|
|
171
|
225 class Load(Instruction):
|
|
252
|
226 def __init__(self, location, value):
|
|
|
227 super().__init__()
|
|
|
228 assert type(value) is Value
|
|
|
229 assert isinstance(location, Value), "Location must be a value"
|
|
|
230 self.value = value
|
|
|
231 self.addDef(value)
|
|
|
232 self.location = location
|
|
|
233 self.addUse(self.location)
|
|
|
234
|
|
|
235 def __repr__(self):
|
|
|
236 return '{} = [{}]'.format(self.value, self.location)
|
|
157
|
237
|
|
261
|
238
|
|
171
|
239 class Store(Instruction):
|
|
252
|
240 def __init__(self, location, value):
|
|
259
|
241 super().__init__()
|
|
|
242 assert type(value) is Value, value
|
|
|
243 assert isinstance(location, Value), "Location must be a value"
|
|
|
244 self.location = location
|
|
|
245 self.value = value
|
|
|
246 self.addUse(value)
|
|
|
247 self.addUse(location)
|
|
|
248
|
|
252
|
249 def __repr__(self):
|
|
|
250 return '[{}] = {}'.format(self.location, self.value)
|
|
|
251
|
|
|
252 def replaceValue(self, old, new):
|
|
|
253 if old is self.value:
|
|
|
254 self.value = new
|
|
|
255 elif old is self.location:
|
|
|
256 self.location = new
|
|
|
257 else:
|
|
|
258 raise Exception()
|
|
|
259 self.removeUse(old)
|
|
|
260 self.addUse(new)
|
|
160
|
261
|
|
261
|
262
|
|
171
|
263 # Branching:
|
|
261
|
264 class Terminator(Instruction):
|
|
|
265 @property
|
|
|
266 def Targets(self):
|
|
|
267 return self.getTargets()
|
|
|
268
|
|
|
269 def changeTarget(self, tfrom, tto):
|
|
|
270 pass
|
|
|
271
|
|
|
272
|
|
177
|
273 class Branch(Terminator):
|
|
219
|
274 def __init__(self, target):
|
|
261
|
275 super().__init__()
|
|
|
276 assert type(target) is BasicBlock
|
|
|
277 self.target = target
|
|
|
278
|
|
219
|
279 def __repr__(self):
|
|
|
280 return 'BRANCH {0}'.format(self.target)
|
|
261
|
281
|
|
219
|
282 def getTargets(self):
|
|
|
283 return [self.target]
|
|
261
|
284
|
|
219
|
285 def changeTarget(self, tfrom, tto):
|
|
|
286 assert tfrom is self.target
|
|
|
287 self.target = tto
|
|
170
|
288
|
|
261
|
289
|
|
177
|
290 class ConditionalBranch(Terminator):
|
|
171
|
291 def __init__(self, a, cond, b, lab1, lab2):
|
|
|
292 super().__init__()
|
|
|
293 self.a = a
|
|
|
294 assert type(a) is Value
|
|
170
|
295 self.cond = cond
|
|
221
|
296 assert cond in ['==', '<', '>']
|
|
171
|
297 self.b = b
|
|
174
|
298 self.addUse(a)
|
|
|
299 self.addUse(b)
|
|
171
|
300 assert type(b) is Value
|
|
|
301 assert type(lab1) is BasicBlock
|
|
170
|
302 self.lab1 = lab1
|
|
171
|
303 assert type(lab2) is BasicBlock
|
|
170
|
304 self.lab2 = lab2
|
|
261
|
305
|
|
170
|
306 def __repr__(self):
|
|
171
|
307 return 'IF {0} {1} {2} THEN {3} ELSE {4}'.format(self.a, self.cond, self.b, self.lab1, self.lab2)
|
|
173
|
308 def getTargets(self):
|
|
|
309 return [self.lab1, self.lab2]
|
|
261
|
310
|
|
177
|
311 def changeTarget(self, tfrom, tto):
|
|
219
|
312 assert tfrom is self.lab1 or tfrom is self.lab2
|
|
177
|
313 if tfrom is self.lab1:
|
|
|
314 self.lab1 = tto
|
|
219
|
315 elif tfrom is self.lab2:
|
|
177
|
316 self.lab2 = tto
|
|
170
|
317
|
|
261
|
318
|
|
|
319 class Return(Terminator):
|
|
|
320 def __init__(self, value=None):
|
|
|
321 super().__init__()
|
|
|
322 self.value = value
|
|
|
323 if value:
|
|
|
324 self.addUse(value)
|
|
|
325
|
|
|
326 def __repr__(self):
|
|
|
327 if self.value:
|
|
|
328 return 'ret {0}'.format(self.value)
|
|
|
329 else:
|
|
|
330 return 'ret'
|
|
|
331
|
|
|
332 def getTargets(self):
|
|
|
333 return []
|
|
|
334
|
|
|
335
|
|
171
|
336 class PhiNode(Instruction):
|
|
252
|
337 def __init__(self):
|
|
|
338 super().__init__()
|
|
|
339 self.incBB = []
|
|
171
|
340
|
|
252
|
341 def addIncoming(self, bb):
|
|
|
342 self.incBB.append(bb)
|
|
|
343
|
