| blob | bef7e2a35463881a1b0b8349487730c6a6ba2016 |
1 require 'voodoo/generators/common_code_generator'
3 module Voodoo
4 # = ARM GNU Assembler Code Generator
5 #
6 # The ARM code generator generates assembly code for use with
7 # the GNU assembler.
8 #
9 # == Calling Convention
10 #
11 # The first four arguments are passed in the registers r0 through r3.
12 # Any additional arguments are passed on the stack, starting at
13 # r13. r13 will always be a multiple of 8.
14 #
15 # The return address for the called function is passed in r14.
16 #
17 # The called function will store its return value in r0.
18 #
19 # The called function is required to preserve the values of registers
20 # r4 through r11 and register r13.
21 #
22 # This calling convention is compatible with the Procedure Call
23 # Standard for the ARM Architecture (AAPCS).
24 #
25 # == Call Frames
26 #
27 # Call frames have the following layout:
28 #
29 # When a function is called, it receives a stack frame that looks like
30 # the following:
31 #
32 # :
33 # old frame
34 # padding
35 # argn
36 # :
37 # arg4 <-- r13 points here
38 #
39 # The function prologue of functions generated by this code generator
40 # creates activiation frames that look as follows:
41 #
42 # :
43 # old frame
44 # padding
45 # argn
46 # :
47 # arg4
48 # saved r14
49 # saved r11
50 # :
51 # saved r4 <-- r13 points here
52 #
53 # == Register Usage
54 #
55 # Inside a function, registers r4..r8, r10, and r11 are used for
56 # local variables and function arguments.
57 #
58 # r12 is used as a temporary, and r3 is used when another temporary
59 # is needed.
60 #
61 class ARMGasGenerator < CommonCodeGenerator
62 def initialize params
63 @WORDSIZE = 4
64 @CODE_ALIGNMENT = 4
65 @DATA_ALIGNMENT = @WORDSIZE
66 @FUNCTION_ALIGNMENT = @WORDSIZE
68 @NREGISTER_ARGS = 4
69 @NREGISTER_LOCALS = 7
70 @RETURN = :r0
71 @TEMPORARY = :r12
72 @constants = []
73 @frame_offset = 0
74 @frame_size = 0
75 @function_end_label = nil
76 @imports = {}
77 @if_labels = []
78 @saved_registers = []
79 super params
80 @output_file_suffix = '.s'
81 end
83 # Create an entry in the constants table,
84 # returning the label that will refer to the constant.
85 # The value may be an integer or a label.
86 def add_constant value
87 label = gensym
88 @constants << [label, value]
89 label
90 end
92 def align alignment = nil
93 unless alignment
94 # Get default alignment
95 case @section
96 when :code
97 alignment = @CODE_ALIGNMENT
98 when :data
99 alignment = @DATA_ALIGNMENT
100 when :function
101 alignment = @FUNCTION_ALIGNMENT
102 else
103 # Use data alignment as default
104 alignment = @DATA_ALIGNMENT
105 end
106 end
107 emit ".align #{alignment}\n" unless alignment == 0
108 end
110 # Returns an sp-relative reference for the nth (0-based) argument.
111 def arg_reference n
112 "[sp, \##{@frame_size + (n - @NREGISTER_ARGS) * @WORDSIZE}]"
113 end
115 # Return the register in which the nth (0-based) argument is stored, or
116 # nil if not stored in a register
117 def arg_register n
118 # The first @NREGISTER_ARGS arguments are in the v registers,
119 # the rest are on the stack.
120 if register_arg? n
121 "v#{n + 1}"
122 else
123 nil
124 end
125 end
127 # Test if op is a binary operation
128 def assymetric_binop? op
129 [:asr, :bsr, :div, :mod, :rol, :ror, :shl, :shr, :sub].member?(op)
130 end
132 # Test if a value is an at-expression
133 def at_expr? value
134 value.respond_to?(:[]) && value[0] == :'@'
135 end
137 # Begins a new block.
138 def begin_block *code
139 emit "# begin block\n"
140 # If we are starting a block at top level, create a frame
141 if @environment == @top_level
142 nlocals = count_locals code
143 create_frame nlocals, false
144 end
145 @environment = Environment.new @environment
146 end
148 # Emit function prologue and declare _formals_ as function arguments
149 def begin_function formals, nlocals
150 if @environment != @top_level
151 raise "Can only begin a function at top level"
152 end
154 @function_end_label = gensym
155 emit "# function #{formals.join ' '}\n"
156 environment = Environment.new @environment
157 environment.add_args formals
158 @environment = environment
159 emit_function_prologue formals, nlocals
160 end
162 # Test if op is a binary operation
163 def binop? op
164 assymetric_binop?(op) || symmetric_binop?(op)
165 end
167 # Define a byte with the given value
168 def byte value
169 emit ".byte #{value}\n"
170 end
172 # Call a function.
173 def call func, *args
174 emit "# call #{func} #{args.join ' '}\n"
176 # Calculate how many arguments need to be pushed on
177 # the stack, and allocate space for them.
178 nstack_args = number_of_stack_arguments args.length
179 old_frame_offset = @frame_offset
180 old_frame_size = @frame_size
181 grow_frame nstack_args if nstack_args > 0
182 $stderr.puts "@frame_size was #{old_frame_size}, is now #{@frame_size}"
184 # Put stack arguments on the stack
185 (@NREGISTER_ARGS...args.length).each do |n|
186 load_value_into_register args[n], @TEMPORARY
187 emit "str #{@TEMPORARY}, " +
188 "[sp , \##{(n - @NREGISTER_ARGS) * @WORDSIZE}]\n"
189 end
191 # Put register arguments in the right registers
192 nregister_args = number_of_register_arguments args.length
193 nregister_args.times do |n|
194 load_value_into_register args[n], :"a#{n + 1}"
195 end
197 # Call function
198 if global? func
199 emit "bl #{func}\n"
200 else
201 func_reg = load_value func
202 emit "blx #{func_reg}\n"
203 end
205 # Restore original stack frame
206 if old_frame_size != @frame_size
207 emit "add sp, sp, \##{@frame_size - old_frame_size}\n"
208 @frame_offset = old_frame_offset
209 @frame_size = old_frame_size
210 end
211 end
213 # Creates a stack frame for the given number of arguments
214 # and local variables.
215 def create_frame nvars, save_lr = true
216 # Calculate how many variables we will store in registers,
217 # and how many on the stack.
218 nregister_vars = [nvars, @NREGISTER_LOCALS].min
219 nstack_vars = nvars - nregister_vars
221 # Save the registers we will clobber to the stack.
222 clobbered = []
223 nregister_vars.times do |i|
224 clobbered << :"v#{i < 5 ? i + 1 : i + 2}"
225 end
226 clobbered << :lr if save_lr
227 @saved_registers = clobbered
228 emit "stmfd sp!, {#{clobbered.join ', '}}\n"
230 # Calculate frame size so that the stack pointer will
231 # be properly aligned at the end of emit_function_prologue.
232 @frame_size = (clobbered.length + nstack_vars) * @WORDSIZE
233 if @frame_size % 8 != 0
234 @frame_size = (@frame_size + 7) / 8 * 8
235 end
236 extra_space = @frame_size - clobbered.length * @WORDSIZE
237 if extra_space > 0
238 emit "sub sp, sp, \##{extra_space}\n"
239 end
240 @frame_offset = 0
241 end
243 # Start a conditional using the specified branch instruction
244 # after the comparison.
245 def common_if comp, x, y = nil
246 emit "# #{comp} #{x} #{y}\n"
248 xreg = load_value x, @TEMPORARY
249 yreg = load_value y, :a4
251 falselabel = @environment.gensym
252 @if_labels.push falselabel
254 emit "cmp #{xreg}, #{yreg}\n"
256 lut = { :ifeq => "bne", :ifge => "blt", :ifgt => "ble",
257 :ifle => "bgt", :iflt => "bge", :ifne => "beq" }
258 emit "#{lut[comp]} #{falselabel}\n"
259 end
261 # Counts the number of local variables created in
262 # a sequence of statements.
263 def count_locals statements
264 count = 0
265 each_statement(statements) do |statement|
266 if statement[0] == :let
267 # let introduces a single local
268 count = count + 1
269 end
270 end
271 count
272 end
274 # Writes any constants that need to be written to the instruction
275 # stream, and clears the list of constants that need to be written.
276 def emit_constants
277 @constants.each do |x|
278 label x[0]
279 word x[1]
280 end
281 @constants = []
282 end
284 # Emit function prologue.
285 def emit_function_prologue formals = [], nlocals = 0
286 # Calculate the number of arguments we were passed in
287 # registers, the total number of values we need to save
288 # on the stack, then create a stack frame and save
289 # the v registers we will be using.
290 nregister_args = [formals.length, @NREGISTER_ARGS].min
291 nvars = nregister_args + nlocals
292 create_frame nvars, true
294 # Move arguments that were passed in registers into
295 # callee-save registers.
296 nregister_args.times do |i|
297 emit "cpy v#{i + 1}, a#{i + 1}\n"
298 end
299 end
301 # Ends the current block.
302 def end_block
303 emit "# end block\n"
305 # If we are returning to top level, restore stack pointer
306 # and saved registers.
307 if @environment.parent == @top_level
308 offset = @frame_size - @saved_registers.length * @WORDSIZE
309 if offset > 0
310 emit "add sp, sp, \##{offset}\n"
311 end
312 emit "ldmfd sp!, {#{@saved_registers.join ', '}}\n"
313 @frame_size = 0
314 @frame_offset = 0
315 @saved_registers = []
317 # If we need to emit constants, do so now
318 unless @constants.empty?
319 lbl = gensym
320 goto lbl
321 label lbl
322 end
323 end
325 # Restore old value of @environment
326 @environment = @environment.parent
327 end
329 # Ends a function body.
330 def end_function
331 if @environment == @top_level
332 raise "Cannot end function when not in a function"
333 end
335 emit "# function epilogue\n"
336 label @function_end_label
338 # Set sp back to where saved registers were stored
339 saved = @saved_registers
340 offset = @frame_size - saved.length * @WORDSIZE
341 if offset != 0
342 emit "add sp, sp, \##{offset}\n"
343 end
345 # Restore saved registers, putting the old value of lr
346 # in pc so that we return from the function
347 $stderr.puts "Saved registers: #{saved.inspect}"
348 saved[saved.index(:lr)] = :pc
349 emit "ldmfd sp!, {#{saved.join ', '}}\n"
350 @frame_size = 0
351 @frame_offset = 0
352 @saved_registers = []
354 emit_constants
356 emit "# end function\n\n"
358 @environment = @top_level
359 end
361 # Ends a conditional.
362 def end_if
363 label @if_labels.pop
364 end
366 # Evaluate the binary operation expr and store the result in register
367 def eval_binop expr, register
368 x = load_value expr[1], :a4
369 y = load_value expr[2], @TEMPORARY
371 case expr[0]
372 when :bsr
373 emit "lsr #{register}, #{x}, #{y}\n"
374 when :div
375 raise "TODO: Not implemented yet"
376 when :mod
377 raise "TODO: Not implemented yet"
378 when :or
379 emit "orr #{register}, #{x}, #{y}\n"
380 when :shl
381 emit "lsl #{register}, #{x}, #{y}\n"
382 when :shr
383 emit "lsr #{register}, #{x}, #{y}\n"
384 when :xor
385 emit "eor #{register}, #{x}, #{y}\n"
386 else
387 emit "#{expr[0]} #{register}, #{x}, #{y}\n"
388 end
389 end
391 # Evaluates the expression +expr+ and stores the result in +register+.
392 def eval_expr expr, register
393 if expr.length == 1
394 # Load value
395 load_value_into_register expr[0], register
396 else
397 # Evaluate expression
398 op = expr[0]
399 case op
400 when :call
401 call *expr[1..-1]
402 emit "cpy #{register}, #{@RETURN}\n" if register != @RETURN
403 when :'get-byte'
404 get_byte expr[1], expr[2], register
405 when :'get-word'
406 get_word expr[1], expr[2], register
407 when :not
408 load_value_into_register expr[1], register
409 emit "mvn #{@TEMPORARY}, #0\n"
410 emit "eor #{register}, #{register}, #{@TEMPORARY}\n"
411 else
412 if binop? op
413 eval_binop expr, register
414 else
415 raise "Not a magic word: #{op}"
416 end
417 end
418 end
419 end
421 # Export symbols from the current section
422 def export *symbols
423 symbols.each { |sym| emit ".globl #{sym}\n" }
424 end
426 # Add a function to the current section
427 def function formals, *code
428 nlocals = count_locals code
429 begin_function formals, nlocals
430 code.each { |action| add section, action }
431 end_function
432 end
434 # Load byte from _base_ + _offset_ into _register_
435 def get_byte base, offset, register
436 # If base is an integer, but offset isn't, swap them
437 if !integer?(offset) && integer?(base)
438 base, offset = [offset, base]
439 end
441 if integer? offset
442 base_reg = load_value base
443 if offset == 0
444 emit "ldrb #{register}, [#{base_reg}]\n"
445 else
446 emit "ldrb #{register}, [#{base_reg}, \##{offset}]\n"
447 end
448 else
449 base_reg = load_value base
450 offset_reg = load_value offset, :a4
451 emit "ldrb #{register}, [#{base_reg}, #{offset_reg}]\n"
452 end
453 end
455 # Load word from _base_ + _offset_ * _@WORDSIZE_ into _register_
456 def get_word base, offset, register
457 if integer? offset
458 base_reg = load_value base
459 if offset == 0
460 emit "ldr #{register}, [#{base_reg}]\n"
461 else
462 emit "ldr #{register}, [#{base_reg}, \##{offset * @WORDSIZE}]\n"
463 end
464 else
465 base_reg = load_value base
466 offset_reg = load_value offset, :a4
467 emit "ldr #{register}, [#{base_reg}, #{offset_reg}, LSL #2]\n"
468 end
469 end
471 # Test if a symbol refers to a global
472 def global? symbol
473 symbol?(symbol) && @environment[symbol] == nil
474 end
476 # Jump to a label.
477 def goto label
478 emit "b #{label}\n"
480 # If we have constants that need to be emitted, do so now
481 emit_constants
482 end
484 # Grows the current frame by n words, plus padding to
485 # respect alignment rules.
486 def grow_frame nwords
487 increment = (nwords * @WORDSIZE + 7) / 8 * 8
488 emit "sub sp, sp, \##{increment}\n"
489 @frame_size = @frame_size + increment
490 @frame_offset = @frame_offset + increment
491 end
493 # Start the false path of a conditional.
494 def ifelse
495 emit "# else\n"
496 newlabel = @environment.gensym
497 goto newlabel
498 lbl = @if_labels.pop
499 label lbl
500 @if_labels.push newlabel
501 end
503 # Test if x is equal to y
504 def ifeq x, y
505 common_if :ifeq, x, y
506 end
508 # Test if x is greater than or equal to y
509 def ifge x, y
510 common_if :ifge, x, y
511 end
513 # Test if x is strictly greater than y
514 def ifgt x, y
515 common_if :ifgt, x, y
516 end
518 # Test if x is less than or equal to y
519 def ifle x, y
520 common_if :ifle, x, y
521 end
523 # Test if x is strictly less than y
524 def iflt x, y
525 common_if :iflt, x, y
526 end
528 # Test if x different from y
529 def ifne x, y
530 common_if :ifne, x, y
531 end
533 # Import labels into the current section
534 def import *symbols
535 # Record imported labels in @imports
536 symbols.each { |sym| @imports[sym] = sym }
537 end
539 # Test if a value is an integer
540 def integer? value
541 value.kind_of? Integer
542 end
544 # Emit a label
545 def label name
546 emit "#{name}:\n"
547 end
549 # Introduce a new local variable
550 def let symbol, *expr
551 emit "# let #{symbol} #{expr.join ' '}\n"
552 n = @environment.locals
553 @environment.add_local symbol
555 register = local_register n
556 if register
557 # We will use a register to store the value
558 eval_expr expr, register
559 else
560 # We will use the stack to store the value
561 ref = local_reference n
562 eval_expr expr, @TEMPORARY
563 emit "str #{@TEMPORARY}, #{ref}\n"
564 end
565 end
567 # Load the value at the given address.
568 def load_at address, register = @TEMPORARY
569 load_value_into_register address, register
570 emit "ldr #{register}, [#{register}]\n"
571 register
572 end
574 # Load a value into a register.
575 # Returns the name of the register.
576 # If the value was already in a register, the name of that
577 # register is returned.
578 # Else, the value is loaded into a register and the name of
579 # that register is returned. The register to use in that case
580 # may be specified using the optional second argument.
581 def load_value x, register = @TEMPORARY
582 if integer? x
583 if x >= 0 && x <= 255
584 emit "mov #{register}, \##{x}\n"
585 return register
586 elsif x >= -255 && x < 0
587 emit "mvn #{register}, \##{-(x + 1)}\n"
588 return register
589 else
590 lbl = add_constant x
591 emit "ldr #{register}, #{lbl}\n"
592 return register
593 end
594 elsif symbol? x
595 binding = @environment[x]
596 if binding
597 case binding[0]
598 when :arg
599 n = binding[1]
600 if register_arg? n
601 return arg_register(n)
602 else
603 emit "ldr #{register}, #{arg_reference binding[1]}\n"
604 return register
605 end
606 when :local
607 n = binding[1]
608 if register_local? n
609 return local_register(n)
610 else
611 emit "ldr #{register}, #{local_reference n}\n"
612 return register
613 end
614 else
615 raise "Don't know how to load #{x.inspect}"
616 end
617 else
618 # Assume global
619 lbl = add_constant x
620 emit "ldr #{register}, #{lbl}\n"
621 return register
622 end
623 elsif at_expr? x
624 load_at x[1], register
625 else
626 raise "Don't know how to load #{x.inspect}"
627 end
628 end
630 # Load a value into a specific register
631 def load_value_into_register x, register
632 reg = load_value x, register
633 if reg != register
634 emit "cpy #{register}, #{reg}\n"
635 end
636 end
638 # Returns an sp-relative reference for the nth (0-based) local.
639 def local_reference n
640 "[sp, \##{@frame_offset + (number_of_register_arguments + n) * @WORDSIZE}]"
641 end
643 # Return the register in which the nth local (0-based) is stored, or
644 # nil if not stored in a register
645 def local_register n
646 if register_local? n
647 n = n + number_of_register_arguments
648 if n < 5
649 "v#{n + 1}"
650 else
651 "v#{n + 2}"
652 end
653 else
654 nil
655 end
656 end
658 # Calculate the number of register arguments,
659 # given the total number of arguments.
660 def number_of_register_arguments n = @environment.args
661 [n, @NREGISTER_ARGS].min
662 end
664 # Calculate the number of stack arguments,
665 # given the total number of arguments.
666 def number_of_stack_arguments n = @environment.args
667 [0, n - @NREGISTER_ARGS].max
668 end
670 # Returns true if the nth (0-based) argument is stored in a register
671 def register_arg? n
672 n < @NREGISTER_ARGS
673 end
675 # Returns true if the nth (0-based) local is stored in a register
676 def register_local? n
677 (n + number_of_register_arguments) < @NREGISTER_LOCALS
678 end
680 # Returns from a function.
681 #
682 # _words_ may contain an expression to be evaluated. The result
683 # of the evaluation is returned from the function.
684 def ret *words
685 emit "# return #{words.join ' '}\n"
686 # Compute return value and store it in @RETURN
687 eval_expr(words, @RETURN) unless words.empty?
688 # Go to epilogue
689 goto @function_end_label
690 end
692 # Set a variable to the result of evaluating an expression
693 def set symbol, *expr
694 emit "# set #{symbol} #{expr.join ' '}\n"
696 x = @environment[symbol]
697 if x == nil
698 raise "Cannot change value of constant #{symbol}"
699 end
701 register = nil
702 case x[0]
703 when :arg
704 register = arg_register x[1]
705 when :local
706 register = local_register x[1]
707 end
709 if register
710 # Set new value
711 eval_expr expr, register
712 else
713 case x[0]
714 when :local
715 ref = local_reference x[1]
716 when :arg
717 ref = arg_reference x[1]
718 else
719 raise "??? #{sym} is neither a local nor an argument"
720 end
721 eval_expr expr, @TEMPORARY
722 emit "str #{@TEMPORARY}, #{ref}\n"
723 end
724 end
726 # Set the byte at _base_ + _offset_ to _value_
727 def set_byte base, offset, value
728 emit "# set-byte #{base} #{offset} #{value}\n"
729 # If base is an integer, but offset isn't, swap them
730 if !integer?(offset) && integer?(base)
731 base, offset = [offset, base]
732 end
734 if integer? offset
735 base_reg = load_value base, :a4
736 load_value_into_register value, @TEMPORARY
737 if offset == 0
738 emit "strb #{@TEMPORARY}, [#{base_reg}]\n"
739 else
740 emit "strb #{@TEMPORARY}, [#{base_reg}, \##{offset}]\n"
741 end
742 else
743 eval_binop [:add, base, offset], :a4
744 load_value_into_register value, @TEMPORARY
745 emit "strb #{@TEMPORARY}, [a4]\n"
746 end
747 end
749 # Set the word at _base_ + _offset_ * +@WORDSIZE+ to _value_
750 def set_word base, offset, value
751 emit "# set-word #{base} #{offset} #{value}\n"
752 # If base is an integer, but offset isn't, swap them
753 if !integer?(offset) && integer?(base)
754 base, offset = [offset, base]
755 end
757 if integer? offset
758 base_reg = load_value base, :a4
759 load_value_into_register value, @TEMPORARY
760 if offset == 0
761 emit "str #{@TEMPORARY}, [#{base_reg}]\n"
762 else
763 emit "str #{@TEMPORARY}, [#{base_reg}, \##{offset * @WORDSIZE}]\n"
764 end
765 else
766 load_value_into_register base, :a4
767 load_value_into_register offset, @TEMPORARY
768 emit "add a4, a4, #{@TEMPORARY}, LSL #2\n"
769 load_value_into_register value, @TEMPORARY
770 emit "str #{@TEMPORARY}, [a4]\n"
771 end
772 end
774 # Define a string with the given value
775 def string value
776 code = ''
777 value.each_byte do |b|
778 if b == 92
779 code << "\\\\"
780 elsif b >= 32 && b < 127 && b != 34
781 code << b.chr
782 else
783 code << sprintf("\\%03o", b)
784 end
785 end
786 emit ".ascii \"#{code}\"\n"
787 end
789 # Test if a value is a symbol
790 def symbol? value
791 value.kind_of? Symbol
792 end
794 # Test if op is a symmetric binary operation (i.e. it will yield the
795 # same result if the order of its source operands is changed).
796 def symmetric_binop? op
797 [:add, :and, :mul, :or, :xor].member? op
798 end
800 # Call a function, re-using the current call frame if possible.
801 def tail_call func, *args
802 emit "# tail-call #{func} #{args.join ' '}\n"
804 # TODO: Implement proper tail calls
805 ret :call, func, *args
806 end
808 # Define a word with the given value
809 def word value
810 emit ".int #{value}\n"
811 end
813 # Write generated code to the given IO object.
814 def write io
815 @sections.each do |section,code|
816 unless code.empty?
817 io.puts ".section #{section.to_s}"
818 io.puts code
819 io.puts
820 end
821 end
822 end
824 end
826 # Register class for little endian ARM
827 Voodoo::CodeGenerator.register_generator ARMGasGenerator,
828 :architecture => :arm,
829 :format => :gas
830 end