Re: Contest #2... Example Programs
- Posted by PeteE Dec 14, 2010
- 2525 views
I do the label fixup very differently. each time my assembler hit a forward reference to a label it reserve a fixed number of code instructions. Derek and Matt assembler use addition of power of 2, mine use power of tens. I reserve a register to hold number 10 and multiply the targer register with that number. I grow the address by a serie of "addi Rt n" and "mult Rt Rm". It doesn't need a second pass to fix the labels. When a label is met in the code the assembler immediatly lookup the pending fix and resolve them. There is 2 limitations to my system: to space allocated is always the same so it is oversized for small address. Secondly It limit the program address space to 0 - 9999. I could increase it but it would means more space lost.
Very interesting, Jacques. I took another different approach to resolving labels in my (unreleased) cpu assembler. Instead of powers of 2 or 10, I wrote a general purpose function to generate instructions to load an arbitrary integer into a register using add and mul operations. To generate a jump offset, it loads the address of the label into the register using that function. For example, to load 999 into a register, the instructions emitted are:
289 r8=9 484 r8*=4 (36) 381 r8+=1 (37) 483 r8*=3 (111) 483 r8*=3 (333) 483 r8*=3 (999)
There's an obvious optimization missed there: it should use a *=9 instead of two *=3. There's also a problem when there's a backward reference and forward reference that overlap: the size of the label loads may shift the label address up and down, and the assembler doesn't terminate until the label addresses stop fluctuating. One solution is to manually put nops into the code in random places to try to get it to converge, but requires luck. I ended up making the assembler insert nops for me to keep a label address fixed when it takes too many tries to get them to settle.
It was rainy here too in Oregon this past weekend. I initially wasn't going to write my own assembler for a cpu that won't be used after a week, but it turns out I couldn't resist. I'll post the code later tonight.
Edit: and here it is. I also solved that number optimization bug.
-- User: PeteE -- Contest 2 virtual machine assembler -- Usage: vmasm.ex prog.src > prog.cpu include std/io.e include std/text.e include std/cmdline.e include std/convert.e include std/map.e as map include std/regex.e as re re:regex set_val = re:new(`^r([0-9])=(-?[0-9]+)`), set_reg = re:new(`^r([0-9])=r([0-9])`), add = re:new(`^r([0-9])\+=([0-9])`), add_reg = re:new(`^r([0-9])\+=r([0-9])`), mul = re:new(`^r([0-9])\*=([0-9])`), mul_reg = re:new(`^r([0-9])\*=r([0-9])`), load = re:new(`^r([0-9])=\[r([0-9])\]`), store = re:new(`^\[r([0-9])\]=r([0-9])`), set_lbl = re:new(`^r([0-9])=@([A-Za-z0-9_]+)`), if_reg = re:new(`^if r([0-9]) ([A-Za-z0-9_]+)`), a_label = re:new(`^([A-Za-z0-9_]+):`), halt = re:new(`^halt`), nop = re:new(`^nop`) map:map nums = map:new() -- memoized num() -- return a sequence of instructions which load the value n into a register r function num(integer r, integer n, integer limit) sequence result, tmp if n < 0 then result = {sprintf("2%s0 r%s=0",{r,r}), sprintf("8%s%s r%s=[r%s] (-1)",{r,r,r,r})} if n != -1 then result &= num(r, -n, 0) result[3][1] = '4' -- convert first set op to a mul result[3] = insert(result[3], '*', 7) end if return result end if result = map:get(nums, n, {}) if length(result) then -- we've seen n before for i = 1 to length(result) do result[i][2] = r -- rewrite the dest register result[i][6] = r end for return result elsif n >= 0 and n <= 9 then result = {sprintf("2%s%d r%s=%d",{r,n,r,n})} elsif limit = 0 or limit > 2 then if limit != 0 then limit -= 1 end if for i = 2 to 9 do -- factors if i*floor(n/i) = n then tmp = num(r, floor(n/i), limit) if length(tmp) then tmp &= {sprintf("4%s%d r%s*=%d (%d)", {r,i,r,i,n})} if limit = 0 or length(tmp) < limit then result = tmp limit = length(tmp) end if end if end if end for for i = 1 to 9 do -- sums tmp = num(r, n-i, limit) if length(tmp) then tmp &= {sprintf("3%s%d r%s+=%d (%d)", {r,i,r,i,n})} if limit = 0 or length(tmp) < limit then result = tmp limit = length(tmp) end if end if end for end if map:put(nums, n, result) -- memoize this result return result end function function assemble(sequence prog) sequence s object ref integer n = 0, done = 0, tries = 0 map:map labels = map:new() for i = 1 to length(prog) do prog[i] = trim(prog[i]) end for -- first pass: assemble instructions and remove blank lines n = 1 while n <= length(prog) do s = prog[n] if length(s) = 0 then prog = remove(prog, n) continue end if ref = re:find(if_reg, s) if sequence(ref) then s = {"r9=@" & s[ref[3][1]..ref[3][2]], "09" & s[ref[2][1]] & " " & s} prog = replace(prog, s, n) n += 2 continue end if ref = re:find(set_val, s) if sequence(ref) then s = num(s[ref[2][1]], to_integer(s[ref[3][1]..ref[3][2]]), 0) s[1] &= prog[n][ref[1][2]+1..$] prog = replace(prog, s, n) n += length(s) continue end if s = re:find_replace(add, s, `3\1\2 r\1+=\2`) s = re:find_replace(mul, s, `4\1\2 r\1*=\2`) s = re:find_replace(set_reg, s, `5\1\2 r\1=r\2`) s = re:find_replace(add_reg, s, `6\1\2 r\1+=r\2`) s = re:find_replace(mul_reg, s, `7\1\2 r\1*=r\2`) s = re:find_replace(load, s, `8\1\2 r\1=[r\2]`) s = re:find_replace(store, s, `9\2\1 [r\1]=r\2`) s = re:find_replace(halt, s, `100 halt`) s = re:find_replace(nop, s, `300 nop`) prog[n] = s n += 1 end while -- middle pass: presize label loads and check each label address while not done do done = 1 tries += 1 n = 0 for i = 1 to length(prog) do ref = re:find(a_label, prog[i]) if sequence(ref) then s = prog[i][ref[2][1]..ref[2][2]] if map:get(labels, s, -1) != n then -- recalculate label if tries > 20 and map:get(labels, s) = n + 1 then n = map:get(labels, s) + 1 -- give up and pad later with nops elsif tries > 30 and map:get(labels, s) > n then n = map:get(labels, s) + 1 -- give up and pad later with nops else done = 0 --if length(num('0', n, 0)) > length(num('0', n+1, 0)) and tries < 10 then -- n += 1 --end if map:put(labels, s, n) end if --printf(2, "%s is %d\n", {s, n}) end if continue end if ref = re:find(set_lbl, prog[i]) if sequence(ref) then s = prog[i][ref[3][1]..ref[3][2]] n += length(num('0', map:get(labels, s), 0)) continue end if n += 1 end for end while --printf(2, "tries=%d\n", tries) -- final pass: assemble label loads and remove labels n = 1 while n <= length(prog) do ref = re:find(set_lbl, prog[n]) if sequence(ref) then s = prog[n][ref[3][1]..ref[3][2]] if not map:has(labels, s) then printf(2, "undefined label: %s\n", {s}) abort(1) end if s = num(prog[n][ref[2][1]], map:get(labels, s), 0) s[1] &= prog[n][ref[1][2]+1..$] prog = replace(prog, s, n) n += length(s) continue end if ref = re:find(a_label, prog[n]) if sequence(ref) then s = prog[n][ref[2][1]..ref[2][2]] --printf(2,"label %s is at %d n is %d\n", {s, map:get(labels, s), n}) s = repeat("300 nop", map:get(labels, s) - n + 1) -- nop padding prog = replace(prog, s, n) n += length(s) continue end if n += 1 end while return prog end function constant cmd_line = command_line() write_lines(1, assemble(read_lines(cmd_line[3])))