Mercurial > lcfOS

comparison python/codegenarm.py @ 269:5f8c04a8d26b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Towards better modularity
author Windel Bouwman
date Sun, 18 Aug 2013 17:43:18 +0200
parents 5ec7580976d9
children cdc76d183bcc
comparison
equal deleted inserted replaced
268:5ec7580976d9 269:5f8c04a8d26b
1 import logging 1 import logging
2 import ir 2 import ir
3 from target import Label, Comment, Alignment, LabelRef, Imm32, DebugInfo 3 from target import Label, Comment, Alignment, LabelRef, Imm32, DebugInfo
4 import cortexm3 as arm 4 import cortexm3 as arm
5 from ppci import CompilerError 5 from ppci import CompilerError
6 import irmach 6 import graph
7 7 import flowgraph
8 8 import registerallocator
9 class InstructionSelector: 9 from instructionselector import InstructionSelector
10 def newTmp(self):
11 return 't999'
12
13 def munchProgram(self, p):
14 assert isinstance(p, ir.Module)
15 self.result = []
16 for f in p.Functions:
17 for bb in f.BasicBlocks:
18 for i in bb.Instructions:
19 self.munchStm(i)
20 return self.result
21
22 def emit(self, *args, **kwargs):
23 """ Abstract instruction emitter """
24 i = irmach.AbstractInstruction(*args, **kwargs)
25 self.result.append(i)
26
27 def munchStm(self, s):
28 raise NotImplementedError()
29
30 def munchExpr(self, e):
31 raise NotImplementedError()
32
33
34 class RegisterAllocator:
35 """ Target independent register allocator """
36 pass
37 10
38 11
39 class ArmInstructionSelector(InstructionSelector): 12 class ArmInstructionSelector(InstructionSelector):
13 """ Instruction selector for the arm architecture """
40 def munchExpr(self, e): 14 def munchExpr(self, e):
41 if isinstance(e, ir.Alloc): 15 if isinstance(e, ir.Alloc):
42 return 0 16 return 0
43 elif isinstance(e, ir.Binop) and e.operation == '+': 17 elif isinstance(e, ir.Binop) and e.operation == '+':
44 a = self.munchExpr(e.value1) 18 a = self.munchExpr(e.value1)
45 b = self.munchExpr(e.value2) 19 b = self.munchExpr(e.value2)
46 d = self.newTmp() 20 d = self.newTmp()
47 self.emit('add %d0, %s0, %s1', dst=[d], src=[a, b]) 21 self.emit('add %d0, %s0, %s1', dst=[d], src=[a, b])
48 return d 22 return d
23 elif isinstance(e, ir.Binop) and e.operation == '-':
24 a = self.munchExpr(e.value1)
25 b = self.munchExpr(e.value2)
26 d = self.newTmp()
27 self.emit('sub %d0, %s0, %s1', dst=[d], src=[a, b])
28 return d
49 elif isinstance(e, ir.Binop) and e.operation == '|': 29 elif isinstance(e, ir.Binop) and e.operation == '|':
50 a = self.munchExpr(e.value1) 30 a = self.munchExpr(e.value1)
51 b = self.munchExpr(e.value2) 31 b = self.munchExpr(e.value2)
52 d = self.newTmp() 32 d = self.newTmp()
53 self.emit('orrrr %d0, %s0, %s1', dst=[d], src=[a, b]) 33 self.emit('or %d0, %s0, %s1', dst=[d], src=[a, b])
54 return d 34 return d
55 elif isinstance(e, ir.Binop) and e.operation == '<<': 35 elif isinstance(e, ir.Binop) and e.operation == '<<':
56 a = self.munchExpr(e.value1) 36 a = self.munchExpr(e.value1)
57 b = self.munchExpr(e.value2) 37 b = self.munchExpr(e.value2)
58 d = self.newTmp() 38 d = self.newTmp()
60 return d 40 return d
61 elif isinstance(e, ir.Binop) and e.operation == '*': 41 elif isinstance(e, ir.Binop) and e.operation == '*':
62 a = self.munchExpr(e.value1) 42 a = self.munchExpr(e.value1)
63 b = self.munchExpr(e.value2) 43 b = self.munchExpr(e.value2)
64 d = self.newTmp() 44 d = self.newTmp()
65 self.emit('mylll %d0, %s0, %s1', dst=[d], src=[a, b]) 45 self.emit('mul %d0, %s0, %s1', dst=[d], src=[a, b])
66 return d 46 return d
67 elif isinstance(e, ir.Const): 47 elif isinstance(e, ir.Const):
68 d = self.newTmp() 48 d = self.newTmp()
69 if e.value < 256: 49 if e.value < 256:
70 self.emit('ldr %d0, {}'.format(e.value), dst=[d]) 50 self.emit('ldr %d0, {}'.format(e.value), dst=[d])
71 else: 51 else:
72 self.emit('ldrpcrel TODO') 52 self.emit('ldrpcrel TODO', dst=[d])
73 return d 53 return d
74 elif isinstance(e, ir.Mem): 54 elif isinstance(e, ir.Mem):
75 # Load from memory 55 # Load from memory
76 loc = self.munchExpr(e.e) 56 loc = self.munchExpr(e.e)
77 d = self.newTmp() 57 d = self.newTmp()
78 self.emit('ldr %d0, [%s0]', src=[loc], dst=[d]) 58 self.emit('ldr %d0, [%s0]', src=[loc], dst=[d])
79 return d 59 return d
80 elif isinstance(e, ir.Temp): 60 elif isinstance(e, ir.Temp):
81 return e 61 return self.getTempReg(e)
82 else: 62 else:
83 raise NotImplementedError('--> {}'.format(e)) 63 raise NotImplementedError('--> {}'.format(e))
84 64
85 def munchStm(self, s): 65 def munchStm(self, s):
86 if isinstance(s, ir.Move) and isinstance(s.dst, ir.Mem): 66 if isinstance(s, ir.Move) and isinstance(s.dst, ir.Mem):
87 memloc = self.munchExpr(s.dst.e) 67 memloc = self.munchExpr(s.dst.e)
88 val = self.munchExpr(s.src) 68 val = self.munchExpr(s.src)
89 self.emit('str [%s0], %s1') 69 self.emit('str [%s0], %s1')
90 elif isinstance(s, ir.Move) and isinstance(s.dst, ir.Temp): 70 elif isinstance(s, ir.Move) and isinstance(s.dst, ir.Temp):
91 val = self.munchExpr(s.src) 71 val = self.munchExpr(s.src)
92 self.emit('str %d0, %s0', dst=[s.dst], src=[val]) 72 dreg = self.getTempReg(s.dst)
73 self.emit('mov %d0, %s0', dst=[dreg], src=[val])
93 elif isinstance(s, ir.Return): 74 elif isinstance(s, ir.Return):
94 self.emit('ret') 75 #etgt = self.targets[
76 self.emit('jmp exit', jumps=[])
95 elif isinstance(s, ir.Jump): 77 elif isinstance(s, ir.Jump):
96 self.emit('jmp {}'.format(s)) 78 tgt = self.targets[s.target]
79 self.emit('jmp {}'.format(s), jumps=[tgt])
97 elif isinstance(s, ir.CJump): 80 elif isinstance(s, ir.CJump):
98 self.munchExpr(s.a) 81 a = self.munchExpr(s.a)
99 self.munchExpr(s.b) 82 b = self.munchExpr(s.b)
100 self.emit('jmp {}'.format(s)) 83 self.emit('cmp %s0, %s1', src=[a, b])
84 ntgt = self.targets[s.lab_no]
85 ytgt = self.targets[s.lab_yes]
86 jmp_ins = self.makeIns('jmp {}'.format(s.lab_no), jumps=[ntgt])
87 # Explicitely add fallthrough:
88 self.emit('jeq {}'.format(s.lab_yes), jumps=[ytgt, jmp_ins])
89 self.emit2(jmp_ins)
101 else: 90 else:
102 raise NotImplementedError('--> {}'.format(s)) 91 raise NotImplementedError('--> {}'.format(s))
103 92
104 93
105 class ArmCodeGenerator: 94 class ArmCodeGenerator:
106 def __init__(self, outs): 95 def __init__(self, outs):
96 # TODO: schedule traces in better order.
97 # This is optional!
107 self.ins_sel = ArmInstructionSelector() 98 self.ins_sel = ArmInstructionSelector()
108 self.outs = outs 99 self.outs = outs
109 self.outs.getSection('code').address = 0x08000000 100 self.outs.getSection('code').address = 0x08000000
110 self.outs.getSection('data').address = 0x20000000 101 self.outs.getSection('data').address = 0x20000000
111 102
112 def generate(self, ircode): 103 def generate(self, ircode, cfg_file=None, ig_file=None):
113 self.ins_sel.munchProgram(ircode) 104 x = self.ins_sel.munchProgram(ircode)
105 cfg = flowgraph.FlowGraph(x)
106 if cfg_file:
107 cfg.to_dot(cfg_file)
108 ig = registerallocator.InterferenceGraph(cfg)
109 if ig_file:
110 ig.to_dot(ig_file)
111
112 regs = ['r0', 'r1', 'r2', 'r3', 'r4', 'r5', 'r6', 'r7']
113 ra = registerallocator.RegisterAllocator()
114 ra.registerAllocate(ig, regs)
114 115
115 116
116 class ArmCodeGenerator_old:
117 """
118 Simple code generator
119 Ad hoc implementation
120 """
121 def __init__(self, out):
122 self.outs = out
123 self.logger = logging.getLogger('codegenarm')
124
125 def emit(self, item):
126 self.outs.emit(item)
127
128 def generate(self, ircode):
129 assert isinstance(ircode, ir.Module)
130 self.logger.info('Generating arm code for {}'.format(ircode.name))
131 self.available_regs = {arm.r3, arm.r4, arm.r5, arm.r6, arm.r7}
132 self.regmap = {}
133 # TODO: get these from linker descriptor?
134 self.outs.getSection('code').address = 0x08000000
135 self.outs.getSection('data').address = 0x20000000
136 self.outs.selectSection('data')
137
138 for gvar in ircode.Variables:
139 self.emit(Label(gvar.name))
140 # TODO: use initial value:
141 self.dcd(0)
142
143 self.imms = [] # list with immediates relative to PC.
144 self.outs.selectSection('code')
145
146 # Manually inserted startup code:
147 self.dcd(0x20000678) # initial stack ptr
148 # TODO: use label here:
149 #self.emit(arm.dcd_ins(LabelRef('reset'))) # reset vector
150 self.dcd(0x08000009) # reset vector, lsb indicates thumb mode
151 self.emit(arm.bl_ins(LabelRef('main')))
152
153 self.emit(Label('reset'))
154 for f in ircode.Functions:
155 self.localVars = []
156 # Add global variable addresses to immediate list:
157 for gvar in ircode.Variables:
158 pass #self.imms.append((
159
160 self.stack_frame = []
161 self.emit(Label(f.name))
162 # Save some registers:
163 self.emit(arm.push_ins(arm.RegisterSet({arm.r3, arm.r4, arm.r5, arm.r6,arm.r7,arm.lr})))
164 for bb in f.BasicBlocks:
165 self.emit(Label(bb.name))
166 for ins in bb.Instructions:
167 self.generateInstruction(ins)
168
169 self.align()
170 while self.imms:
171 l, v = self.imms.pop()
172 self.emit(Label(l))
173 self.dcd(v)
174 self.align()
175 self.outs.backpatch()
176 self.outs.backpatch()
177 codesize = self.outs.getSection('code').Size
178 self.logger.info('Generated {} bytes code'.format(codesize))
179
180 def dcd(self, x):
181 self.emit(arm.dcd_ins(Imm32(x)))
182
183 def align(self):
184 self.outs.emit(Alignment(4))
185
186 # Helper functions:
187 def getStack(self, v):
188 off = self.stack_frame.index(v)
189 return off * 4
190
191 def addStack(self, v):
192 self.stack_frame.append(v)
193 return self.getStack(v)
194
195 def getGlobal(self, r, g):
196 _global_address = g.name + '__global'
197 self.emit(arm.ldr_pcrel(r, LabelRef(_global_address)))
198
199 def loadStack(self, reg, val):
200 self.emit(arm.ldr_sprel(reg, arm.MemSpRel(self.getStack(val))))
201
202 def getreg(self, v):
203 if not v in self.regmap:
204 self.regmap[v] = self.available_regs.pop()
205 return self.regmap[v]
206
207 def freereg(self, v, ins):
208 if v.lastUse(ins):
209 r = self.regmap.pop(v)
210 assert r not in self.regmap.values()
211 self.available_regs.add(r)
212
213 def comment(self, txt):
214 self.emit(Comment(txt))
215
216 def debugInfo(self, loc):
217 if loc:
218 self.emit(DebugInfo(loc))
219
220 def generateInstruction(self, ins):
221 self.comment(str(ins))
222 if hasattr(ins, 'debugLoc'):
223 self.debugInfo(ins.debugLoc)
224 if type(ins) is ir.Branch:
225 tgt = LabelRef(ins.target.name)
226 self.emit(arm.b_ins(tgt))
227 elif type(ins) is ir.ImmLoad:
228 lname = ins.target.name + '_ivalue'
229 r0 = self.getreg(ins.target)
230 self.emit(arm.ldr_pcrel(r0, LabelRef(lname)))
231 self.imms.append((lname, ins.value))
232 elif type(ins) is ir.Store:
233 # Load value in r0:
234 r0 = self.getreg(ins.value)
235 # store in memory:
236 # TODO: split globals and locals??
237 #self.getGlobal(arm.r1, ins.location)
238 # Horrible hack with localVars
239 if ins.location in self.localVars:
240 # The value was alloc'ed
241 self.emit(arm.str_sprel(r0, arm.MemSpRel(self.getStack(ins.location))))
242 else:
243 r1 = self.getreg(ins.location)
244 self.emit(arm.storeimm5_ins(r0, arm.MemR8Rel(r1, 0)))
245 self.freereg(ins.location, ins)
246 self.freereg(ins.value, ins)
247 elif type(ins) is ir.Load:
248 # TODO: differ global and local??
249 #self.getGlobal(arm.r0, ins.location)
250 r0 = self.getreg(ins.value)
251 if ins.location in self.localVars:
252 self.emit(arm.ldr_sprel(r0, arm.MemSpRel(self.getStack(ins.location))))
253 else:
254 r2 = self.getreg(ins.location)
255 self.emit(arm.loadimm5_ins(r0, arm.MemR8Rel(r2, 0)))
256 self.freereg(ins.location, ins)
257 elif type(ins) is ir.BinaryOperator:
258 # Load operands:
259 r0 = self.getreg(ins.value1)
260 r1 = self.getreg(ins.value2)
261 r2 = self.getreg(ins.result)
262 # do operation:
263 if ins.operation == '+':
264 self.emit(arm.addregs_ins(r2, r0, r1))
265 elif ins.operation == '<<':
266 self.emit(arm.movregreg_ins(r2, r0))
267 self.emit(arm.lslregs_ins(r2, r1))
268 elif ins.operation == '|':
269 self.emit(arm.movregreg_ins(r2, r0))
270 self.emit(arm.orrregs_ins(r2, r1))
271 else:
272 raise NotImplementedError('operation {} not implemented'.format(ins.operation))
273 self.freereg(ins.value1, ins)
274 self.freereg(ins.value2, ins)
275 elif type(ins) is ir.Call:
276 # TODO: prep parameters:
277 self.emit(arm.bl_ins(LabelRef(ins.callee.name)))
278 elif type(ins) is ir.Return:
279 self.emit(arm.pop_ins(arm.RegisterSet({arm.r3, arm.r4, arm.r5, arm.r6, arm.r7, arm.pc})))
280 elif type(ins) is ir.ConditionalBranch:
281 r0 = self.getreg(ins.a)
282 r1 = self.getreg(ins.b)
283 self.emit(arm.cmp_ins(r1, r0))
284 tgt_yes = LabelRef(ins.lab1.name)
285 if ins.cond == '==':
286 self.emit(arm.beq_ins(tgt_yes))
287 elif ins.cond == '<':
288 self.emit(arm.blt_ins(tgt_yes))
289 elif ins.cond == '>':
290 self.emit(arm.bgt_ins(tgt_yes))
291 else:
292 raise NotImplementedError('"{}" not covered'.format(ins.cond))
293 tgt_no = LabelRef(ins.lab2.name)
294 self.emit(arm.b_ins(tgt_no))
295 self.freereg(ins.a, ins)
296 self.freereg(ins.b, ins)
297 elif type(ins) is ir.Alloc:
298 # Local variables are added to stack
299 self.addStack(ins.value)
300 self.localVars.append(ins.value)
301 # load address into variable:
302 else:
303 raise NotImplementedError('IR "{}" not covered'.format(ins))
304
305