Initial commit
[jwcc.git] / lib / backend / blargcpu.lua
1 local outf = io.stderr
2 local maxstack = 0
3 local minstack = 0
4 local labelnum = 0
5
6 local regstate = {
7         r0 = {},
8         r1 = {},
9         r2 = {},
10         r3 = {}
11 }
12
13 local regvars = {}
14
15 function regalloc_reset()
16         regvars = {}
17         for k,v in pairs(regstate) do
18                 regstate[k] = {}
19         end
20 end
21
22 function regalloc_tmp()
23         for k,v in pairs(regstate) do           -- first look for an empty one
24                 if not v.contains then
25                         regstate[k] = { contains = " tmp", name = k, locked = 0 }
26                         table.insert(regvars, regstate[k])
27                         return regstate[k]
28                 end
29         end
30         for k,v in pairs(regstate) do           -- now look for an unlocked variable to evict
31                 if regalloc_unlocked(v) and v.contains ~= " tmp" then
32                         regalloc_evict(v)
33                         regstate[k] = { contains = " tmp", name = k, locked = 0 }
34                         table.insert(regvars, regstate[k])
35                         return regstate[k]
36                 end
37         end
38         for k,v in pairs(regstate) do           -- now look for an unlocked temporary to evict
39                 if regalloc_unlocked(v) then
40                         regalloc_evict(v)
41                         regstate[k] = { contains = " tmp", name = k, locked = 0 }
42                         table.insert(regvars, regstate[k])
43                         return regstate[k]
44                 end
45         end
46         error("register allocator: tried to allocate a temporary, but couldn't find anything to evict")
47 end
48
49 function regalloc_get(var)
50         for k,v in pairs(regvars) do
51                 if v.contains == var then
52                         return v
53                 end
54         end
55         local reg = { contains = var, locked = 0, evicted = true, stackpos = var.stackpos }
56         table.insert(regvars, reg)
57         return reg
58 end
59
60 function regalloc_lock(reg)
61         if reg.evicted then
62                 regalloc_unevict(reg)
63         end
64         reg.locked = reg.locked + 1
65 end
66
67 function regalloc_unlock(reg)
68         assert(reg.locked > 0)
69         reg.locked = reg.locked - 1
70 end
71
72 function regalloc_unlocked(reg)
73         return not reg.locked or reg.locked == 0
74 end
75
76 function regalloc_free(reg)
77         if reg.contains == " tmp" then
78                 for k,v in pairs(regvars) do
79                         if v == reg then
80                                 table.remove(regvars, k)
81                         end
82                 end
83                 regstate[reg.name] = {}
84                 reg.name = nil
85                 reg.contains = nil
86         else
87                 reg.locked = 0
88         end
89 end
90
91 function regalloc_savestate(save)
92         -- store all NON-evicted variables that MIGHT get evicted in the savestate
93         for k,v in pairs(regstate) do
94                 if v.contains and regalloc_unlocked(v) then
95                         save[v] = { var = v, reg = v.name, dirty = v.dirty }
96                 end
97         end
98 end
99
100 function regalloc_restorestate(save)
101         -- restore any variables that got evicted
102         for k,v in pairs(regstate) do
103                 if v.dirty and ((not save[v]) or (not save[v].dirty)) then
104                         regalloc_clean(v)
105                 end
106         end
107         for k,v in pairs(save) do
108                 regalloc_unevict(v.var, v.reg)
109         end
110 end
111
112 function regalloc_printstate()
113         for k,reg in pairs(regstate) do
114                 if not reg.contains then
115                         print(k..": EMPTY")
116                         for k1,v1 in pairs(reg) do
117                                 print(k.."."..tostring(k1)..": "..tostring(v1))
118                         end
119                 else
120                         local name
121                         if reg.contains == " tmp" then
122                                 name = "compiler internal variable"
123                         elseif reg.contains.name then
124                                 name = reg.contains.name
125                         else
126                                 name = "unknown variable"
127                         end
128                         print(k..": "..name.." ("..
129                                 (reg.evicted and "evicted" or "not evicted") .. ", "..
130                                 ((not regalloc_unlocked(reg)) and "locked" or "not locked") .. ", " ..
131                                 (reg.dirty and "dirty" or "clean") .. ")")
132                 end
133         end
134 end
135
136 function regalloc_evict(reg)
137         assert(reg.contains, "can't evict nil")
138         assert(reg.contains ~= " tmp", "tmp eviction not implemented")
139         
140         if reg.dirty then
141                 regalloc_clean(reg)
142         end
143         reg.evicted = true
144         if reg.name then
145                 regstate[reg.name] = {}
146                 reg.name = nil
147         end
148 end
149
150 function regalloc_clean(reg)
151         assert(reg.contains, "can't clean nil")
152         assert(not reg.evicted, "register already evicted?")
153         assert(regalloc_unlocked(reg), "must be unlocked to clean")
154         
155         local name = "unknown variable"
156         if type(reg.contains) == "string" then
157                 name = reg.contains
158         elseif type(reg.contains) == "table" and reg.contains.name then
159                 name = reg.contains.name
160         end
161         name = "`"..name.."'"
162         
163         reg.dirty = false
164         
165         -- first off, look for an easy eviction -- is there an empty register?
166         for k,v in pairs(regstate) do
167                 if not v.contains then
168                         local tmp = regalloc_tmp()
169                         regalloc_lock(tmp)
170                         emit_opcode("mov", tmp.name..", #"..(reg.stackpos-maxstack-1), "easy evict "..name.." to stack")
171                         emit_opcode("add", tmp.name..", sp")
172                         emit_opcode("sto", "["..tmp.name.."], "..reg.name)
173                         regalloc_free(tmp)
174                         return
175                 end
176         end
177         -- damnit, we have to do an in-place evict
178         
179         -- Step 1 -- push rN
180         emit_opcode("push", "sp, "..reg.name, "in-place evict "..name)
181         -- Step 2 -- Move offset from new sp to desired place into rN
182         emit_opcode("mov", reg.name..", #"..(reg.stackpos-maxstack-2))
183         -- Step 3 -- Add sp to result to get an absolute pointer
184         emit_opcode("add", reg.name..", sp")
185         -- Step 4 -- Load sp with original contents of rN
186         emit_opcode("pop", "sp, sp")
187         -- Step 5 -- Store original contents in address now stored in rN
188         emit_opcode("sto", "["..reg.name.."], sp")
189         -- Step 6 -- Move offset to get back to correct sp into sp
190         emit_opcode("mov", "sp, #"..(maxstack-reg.stackpos +1))
191         -- Step 7 -- Add rN to sp; sp is now restored
192         emit_opcode("add", "sp, "..reg.name)
193         -- In this case, the variable is toast. Sorry.
194         regstate[reg.name] = {}
195         reg.evicted = true
196         reg.name = nil
197 end
198
199 function regalloc_unevict(reg, wantreg)
200         assert(reg.contains, "can't unevict a nil pointer")
201         local name = "unknown variable"
202         if type(reg.contains) == "string" then
203                 name = reg.contains
204         elseif type(reg.contains) == "table" and reg.contains.name then
205                 name = reg.contains.name
206         end
207         name = "`"..name.."'"
208         
209         if not reg.evicted and wantreg and wantreg ~= reg.name then
210                 assert(regalloc_unlocked(regstate[wantreg]), "tried to unevict with a locked wantreg")
211                 if regstate[wantreg].contains then
212                         emit_opcode("push", "sp, "..wantreg, "unevict: swap "..name.." and "..wantreg)
213                         emit_opcode("mov", wantreg..", "..reg.name)
214                         emit_opcode("pop", "sp, "..reg.name)
215                         regstate[reg.name] = regstate[wantreg]
216                         regstate[reg.name].name = reg.name
217                         regstate[wantreg] = reg
218                         regstate[wantreg].name = wantreg
219                         return          -- wee!
220                 else
221                         emit_opcode("mov", wantreg..", "..reg.name, "unevict: move "..name.." to "..wantreg)
222                         regstate[reg.name] = {}
223                         regstate[wantreg] = reg
224                         regstate[wantreg].name = wantreg
225                         return          -- double wee!
226                 end
227         elseif not reg.evicted then
228                 return  -- well, if we don't actually have to do anything, ...!
229         else
230                 assert(reg.contains ~= " tmp", "tmp uneviction not implemented")
231                 assert(reg.evicted)
232                 -- find a register
233                 for k,v in pairs(regstate) do   -- look for an empty
234                         if not v.contains and not wantreg then
235                                 wantreg = k
236                         end
237                 end
238                 for k,v in pairs(regstate) do   -- look for a nontmp that's not dirty
239                         if regalloc_unlocked(v) and v.contains ~= " tmp" and not v.dirty and not wantreg then
240                                 regalloc_evict(v)
241                                 wantreg = k
242                         end
243                 end
244                 for k,v in pairs(regstate) do   -- look for any nontmp
245                         if regalloc_unlocked(v) and v.contains ~= " tmp" and not wantreg then
246                                 regalloc_evict(v)
247                                 wantreg = k
248                         end
249                 end
250                 for k,v in pairs(regstate) do   -- look for anything to evict
251                         if regalloc_unlocked(v) and not wantreg then
252                                 regalloc_evict(v)
253                                 wantreg = k
254                         end
255                 end
256                 assert(wantreg and regalloc_unlocked(regstate[wantreg]), "could not find an unlocked register to evict to")
257                 emit_opcode("mov", wantreg..", #"..(reg.stackpos-maxstack-1), "unevict: pull "..name.." from stack to "..wantreg)
258                 emit_opcode("add", wantreg..", sp")
259                 emit_opcode("ldr", wantreg..", ["..wantreg.."]")
260                 reg.name = wantreg
261                 reg.evicted = false
262                 regstate[wantreg] = reg
263                 return
264         end
265         error("something got fucked up")
266 end
267
268 function regalloc_unevict_all_tmp()
269         for k,v in pairs(regvars) do
270                 if v.evicted and v.contains == " tmp" then
271                         regalloc_unevict(v)
272                 end
273         end
274 end
275
276 function regalloc_destroy(variable)
277         for k,v in pairs(regvars) do
278                 if v.contains == variable and not v.evicted then
279                         regstate[v.name] = {}
280                         v.name = nil
281                 end
282         end
283 end
284
285 local cursection = nil
286 function emit(text)
287         outf:write(text.."\n")
288 end
289
290 function emit_section(section)
291         if cursection == section then
292                 return
293         end
294         emit("\t.section "..section)
295         cursection = section
296 end
297
298 function emit_label(label)
299         emit(label..":")
300 end
301
302 function emit_opcode(opcode, params, comment)
303         if comment then
304                 emit("\t"..opcode.."\t"..params.."\t\t\t@ "..comment)
305         else
306                 emit("\t"..opcode.."\t"..params)
307         end
308 end
309
310 local globalvariables = {}
311 function do_globalvariable(var)
312         globalvariables[var.name] = { type = var.vtype }
313         if var.vtype == "int" then
314                 local initializer = var.initializer or 0
315                 emit_section(".bss")
316                 emit_label(var.name)
317                 emit_opcode(".word",tostring(initializer))
318         else
319                 error("unknown variable emit in do_globalvariable")
320         end
321 end
322
323 function do_function(func)
324         local stack = {}
325         
326                 
327         -- First, read in the arguments and register them as being on the stack.
328         for k,v in pairs(func.args) do
329                 stack[-k] = { name = v.name, type = v.type, stackpos = -k }
330                 assert(v.type == "int", "can only handle ints on the stack right now")
331                 minstack = -k
332         end
333         stack[0] = {name = " return address", type = "int" }    -- XXX not actually an int
334         
335         regalloc_reset()
336         emit_section(".text")
337         emit("")
338         emit_opcode(".global", func.name)
339         emit_label(func.name)
340         local emitter = function(expr, emitter)
341                 if expr.type == "stmtlist" then
342                         local origstack = maxstack
343                         local initialized = false
344                         local savestate = {}
345                         regalloc_savestate(savestate)
346                         for k,v in pairs(expr.body) do
347                                 if v.type == "variable" then
348                                         assert(not initialized, "cannot have more variables after stack has been emitted")
349                                         maxstack = maxstack + 1
350                                         stack[maxstack] = { name = v.name, type = v.vtype, initializer = v.initializer, stackpos = maxstack }
351                                 else
352                                         if not initialized and origstack ~= maxstack then
353                                                 local reg = regalloc_tmp()
354                                                 regalloc_lock(reg)
355                                                 emit_opcode("mov", reg.name..", #"..tostring(maxstack-origstack), "increase stack size for variables")
356                                                 emit_opcode("add", "sp, "..reg.name)
357                                                 regalloc_free(reg)
358                                                 for k2,v2 in pairs(stack) do
359                                                         if v2.initializer then
360                                                                 local data = regalloc_tmp()     -- one for the data
361                                                                 local addr = regalloc_tmp()     -- one for the stack address
362                                                                 regalloc_lock(data)
363                                                                 emit_opcode("mov", data.name..", #"..v2.initializer, "initialize variable "..v2.name)
364                                                                 regalloc_lock(addr)
365                                                                 emit_opcode("mov", addr.name..", #"..tostring(k2-maxstack-1))
366                                                                 emit_opcode("add", addr.name..", sp")
367                                                                 emit_opcode("sto", "["..addr.name.."], "..data.name)
368                                                                 regalloc_free(data)
369                                                                 regalloc_free(addr)
370                                                                 v2.initializer = nil
371                                                         end
372                                                 end
373                                                 initialized = true
374                                         end
375                                         local reg = emitter(v, emitter)
376                                         if reg then
377                                                 regalloc_free(reg)
378                                         end
379                                 end
380                         end
381                         if origstack ~= maxstack then
382                                 local reg = regalloc_tmp()
383                                 emit_opcode("mov", reg.name..", #"..tostring(origstack-maxstack), "decrease stack size for variables")
384                                 emit_opcode("add", "sp, "..reg.name)
385                                 regalloc_free(reg)
386                                 maxstack = origstack
387                                 for i=origstack+1,maxstack do
388                                         regalloc_destroy(stack[i])
389                                         stack[i] = nil
390                                 end
391                         end
392                         regalloc_restorestate(savestate)
393                 elseif expr.type == "expression" then
394                         return emitter(expr.value, emitter)
395                 elseif expr.type == "funccall" then
396                         -- push args on the stack from last to first
397                         for arg=table.getn(expr.args),1,-1 do
398                                 local reg = emitter(expr.args[arg], emitter)
399                                 assert(reg, "argument "..arg.." did not return a register")
400                                 regalloc_lock(reg)
401                                 regalloc_unevict_all_tmp()
402                                 emit_opcode("push","sp, "..reg.name, "push argument "..arg.." onto the stack for function call "..expr.name)
403                                 regalloc_free(reg)
404                                 maxstack = maxstack + 1
405                         end
406                         -- meh, I hate fucking around with the allocator's internal state here, XXX
407                         for k,v in pairs(regstate) do
408                                 assert(not(v.contains == " tmp" and not v.evicted), "it's too damn late now to evict tmp")
409                                 if not v.evicted and v.contains then
410                                         regalloc_evict(v)
411                                 end
412                         end
413                         local reg = regalloc_tmp()
414                         regalloc_lock(reg)
415                         emit_opcode("mov",reg.name..", #"..expr.name, "function call "..expr.name)
416                         emit_opcode("call","sp, "..reg.name)
417                         -- first thing: save the return value!
418                         local retv = regalloc_tmp()
419                         regalloc_lock(retv)
420                         if reg.name == "r0" then        -- try hard to get r0 for the return value
421                                 local tmp = reg
422                                 reg = retv
423                                 retv = tmp
424                         end
425                         if retv.name ~= "r0" then       -- wee o_O
426                                 emit_opcode("mov", retv.name..", r0", "grab return value")
427                         end
428                         -- decrement the stack by the number of args
429                         emit_opcode("mov",reg.name..", #-"..table.getn(expr.args), "clean up stack from function call")
430                         emit_opcode("add","sp, "..reg.name)
431                         maxstack = maxstack - table.getn(expr.args)
432                         regalloc_free(reg)
433                         return retv
434                 elseif expr.type == "while" then
435                         local headlabel, taillabel = labelnum, labelnum + 1
436                         local savestate = {}
437                         labelnum = labelnum + 2
438                         emit_label(".L"..headlabel)
439                         -- do expression
440                         local resreg = emitter(expr.expression, emitter)
441                         assert(resreg, "while expression did not return a register")
442                         regalloc_lock(resreg)
443                         local tmp = regalloc_tmp()
444                         emit_opcode("mov",tmp.name..", #0")
445                         emit_opcode("tst",tmp.name..", "..resreg.name)
446                         emit_opcode("moveq","pc, #.L"..taillabel, "conditional break from while")
447                         regalloc_free(resreg)
448                         regalloc_free(tmp)
449                         regalloc_savestate(savestate)
450                         local tmp = emitter(expr.chunk, emitter)
451                         if tmp then
452                                 regalloc_free(tmp)
453                         end
454                         regalloc_restorestate(savestate)
455                         emit_opcode("mov","pc, #.L"..headlabel)
456                         emit_label(".L"..taillabel)
457                 elseif expr.type == "return" then
458                         local reg = emitter(expr.expression, emitter)
459                         assert(reg, "return expression did not return a register")
460                         regalloc_unevict(reg, "r0")
461                         regalloc_lock(reg)
462                         assert(reg.name == "r0", "failed to unevict to r0?")
463                         local tmp = regalloc_tmp()
464                         regalloc_lock(tmp)
465                         emit_opcode("mov", tmp.name..", #-"..maxstack, "clean up stack before return")
466                         emit_opcode("add","sp, "..tmp.name)
467                         emit_opcode("pop","sp, pc", "return")
468                         regalloc_free(tmp)
469                         regalloc_free(reg)
470                 elseif expr.type == "if" then
471                         local taillabel = labelnum
472                         local savestate = {}
473                         labelnum = labelnum + 1
474                         local resreg = emitter(expr.expression, emitter)
475                         assert(resreg, "if expression did not return a register")
476                         regalloc_lock(resreg)
477                         local tmp = regalloc_tmp()
478                         emit_opcode("mov",tmp.name..", #0")
479                         emit_opcode("tst",tmp.name..", "..resreg.name)
480                         emit_opcode("moveq","pc, #.L"..taillabel, "conditional exit from if")
481                         regalloc_free(resreg)
482                         regalloc_free(tmp)
483                         regalloc_savestate(savestate)
484                         local tmp = emitter(expr.chunk, emitter)
485                         if tmp then
486                                 regalloc_free(tmp)
487                         end
488                         regalloc_restorestate(savestate)
489                         emit_label(".L"..taillabel)
490                 elseif expr.type == "operator" and expr.value ~= "=" then
491                         -- an arith oper
492                         local lhs = emitter(expr.left, emitter)
493                         local rhs = emitter(expr.right, emitter)
494                         local tmp
495                         assert(lhs, "lhs did not return a register")
496                         assert(rhs, "rhs did not return a register")
497                         regalloc_lock(lhs)
498                         regalloc_lock(rhs)
499                         if lhs.contains == " tmp" then
500                                 tmp = lhs
501                         elseif rhs.contains == " tmp" then
502                                 tmp = rhs
503                         end
504                         
505                         if expr.value == "==" or expr.value == "<" or expr.value == ">" then
506                                 local predicates = { ["=="] = "eq", ["<"] = "lt", [">"] = "gt" }
507                                 if not tmp then
508                                         tmp = regalloc_tmp()
509                                         regalloc_lock(tmp)
510                                 end
511                                 -- tst is fucking backwards
512                                 emit_opcode("tst",rhs.name..", "..lhs.name, "comparison operator "..expr.value)
513                                 emit_opcode("mov",tmp.name..", #0")
514                                 emit_opcode("mov"..predicates[expr.value], tmp.name..", #1")
515                         elseif expr.value == "+" then
516                                 if not tmp then
517                                         tmp = regalloc_tmp()
518                                         regalloc_lock(tmp)
519                                 end
520                                 if tmp == lhs then
521                                         emit_opcode("add",tmp.name..", "..rhs.name)
522                                 elseif tmp == rhs then
523                                         emit_opcode("add",tmp.name..", "..lhs.name)
524                                 else
525                                         emit_opcode("mov",tmp.name..", "..lhs.name)
526                                         emit_opcode("add",tmp.name..", "..rhs.name)
527                                 end
528                         elseif expr.value == "-" then
529                                 if not tmp then
530                                         tmp = regalloc_tmp()
531                                         regalloc_lock(tmp)
532                                 end
533                                 emit_opcode("not", rhs.name)
534                                 local tmp2 = regalloc_tmp()
535                                 regalloc_lock(tmp2)
536                                 emit_opcode("mov",tmp2.name..", #1")
537                                 emit_opcode("add",rhs.name..", "..tmp2.name)
538                                 regalloc_free(tmp2)
539                                 if tmp == lhs then
540                                         emit_opcode("add",tmp.name..", "..rhs.name)
541                                 elseif tmp == rhs then
542                                         emit_opcode("add",tmp.name..", "..lhs.name)
543                                 else
544                                         emit_opcode("mov",tmp.name..", "..lhs.name)
545                                         emit_opcode("add",tmp.name..", "..rhs.name)
546                                 end
547                         else
548                                 print("Dunno how to handle operator "..expr.value)
549                                 return nil
550                         end
551                         
552                         if lhs ~= tmp then
553                                 regalloc_free(lhs)
554                         end
555                         if rhs ~= tmp then
556                                 regalloc_free(rhs)
557                         end
558                         regalloc_unlock(tmp)
559                         return tmp
560                 elseif expr.type == "operator" and expr.value == "=" then
561                         assert(expr.left.type == "identifier", "lhs has to be an identifier")
562                         local lhs = emitter(expr.left, emitter)
563                         local rhs = emitter(expr.right, emitter)
564                         assert(rhs, "rhs did not return a register")
565                         regalloc_lock(lhs)
566                         regalloc_lock(rhs)
567                         lhs.dirty = true
568                         emit_opcode("mov",lhs.name..", "..rhs.name)
569                         regalloc_free(rhs)
570                         return lhs
571                 elseif expr.type == "identifier" then
572                         -- find the variable on the stack
573                         local var
574                         for k,v in pairs(stack) do
575                                 if v.name == expr.value and not var then
576                                         var = v
577                                 end
578                         end
579                         for k,v in pairs(globalvariables) do
580                                 if v.name == expr.value and not var then
581                                         var = v
582                                 end
583                         end
584                         assert(var, "I have no idea what identifier "..expr.value.." is")
585                         return regalloc_get(var)
586                 elseif expr.type == "number" then
587                         local reg = regalloc_tmp()
588                         regalloc_lock(reg)
589                         emit_opcode("mov", reg.name..", #"..expr.value)
590                         regalloc_unlock(reg)
591                         return reg
592                 else
593                         error("unknown expression type "..expr.type)
594                 end
595         end
596         emitter(func.body, emitter)     -- call into it, and light it off
597         emit_opcode("pop", "sp, pc")
598 end
599
600 function backend(parsetree, outfn)
601         if outfn then
602                 outf = io.open(outfn, "w")
603         else
604                 outf = io.stdout
605         end
606         emit("@ blargCPU output generated by jwcc")
607         for k,v in pairs(parsetree) do
608                 if v.type == "variable" then
609                         do_globalvariable(v)
610                 elseif v.type == "function" then
611                         do_function(v)
612                 else
613                         error("invalid type in global deparse")
614                 end
615         end
616         if outfn then
617                 outf:close()
618         end
619         outf = io.stderr
620 end
This page took 0.11494 seconds and 4 git commands to generate.