1 require 'voodoo/generators/common_code_generator'
5 # = MIPS GNU Assembler Code Generator
7 # The MIPS code generator generates assembly code for use with
10 # == Calling Convention
12 # The first four arguments are passed in the registers $4 through $7.
13 # Any additional arguments are passed on the stack, starting at
14 # $sp + 16. Words $sp through $sp + 12 will be available for the called
15 # function to use. $sp will always be a multiple of 8.
17 # The return address for the called function is passed in $31.
19 # When performing a position-independent call, the address of the called
20 # function is passed in $25.
22 # The called function will store its return value in $2.
24 # The called function is required to preserve the values of registers
25 # $16 through $23 and register $30.
27 # This calling convention is compatible with the System V ELF ABI.
31 # Call frames have the following layout:
33 # When a function is called, it receives a stack frame that looks like
44 # empty0 <-- $sp points here
46 # The function prologue of functions generated by this code generator
47 # creates activation frames that look as follows:
57 # arg0 <-- $fp points here
59 # pointer to Global Offset Table
67 # padding <-- $sp points here
71 # The four empty slots provided by the caller are used to store
72 # arguments 0 through 3 (originally passed in $4 through $7),
75 # The stack frame created below the four slots provided by the caller
76 # contains the following data, in order:
78 # - Saved return address (originally passed in $31), if necessary.
80 # - Saved pointer to global offset table (computed from $25), if necessary.
82 # - Saved value of $fp, if necessary.
84 # - Saved values of caller's locals 0 through 7
85 # (originally in $16 through $23), if necessary.
87 # - Values of our locals > 8, if necessary.
89 # - Padding to align $sp on a multiple of 8, if necessary.
92 # In accordance with the System V ELF ABI for MIPS, the pointer to
93 # the global offset table is calculated as follows:
95 # $gp = _gp_disp + $25
97 # where $gp is the register to store the pointer, $25 is the register
98 # holding the address of the called function, and _gp_disp is the
99 # offset between the beginning of the function and the global offset table.
101 # Callee-Save Registers
103 # Registers $16 through $23 and $28 through $30 are callee-save.
105 # All other registers are caller-save.
107 class MIPSGasGenerator < CommonCodeGenerator
108 def initialize params
110 @WORDSIZE = 1 << @WORDSIZE_BITS
112 @DATA_ALIGNMENT = @WORDSIZE
113 @STACK_ALIGNMENT_BITS = 3
114 @STACK_ALIGNMENT = 1 << @STACK_ALIGNMENT_BITS
115 @FP_OFFSET = -3 * @WORDSIZE
116 @FUNCTION_ALIGNMENT = @WORDSIZE
117 @GP_OFFSET = -2 * @WORDSIZE
118 @INITIAL_FRAME_SIZE = 4 * @WORDSIZE
119 @REGISTER_ARG_BASE = 4
121 @LOCAL_REGISTERS = [:'$16', :'$17', :'$18', :'$19',
122 :'$20', :'$21', :'$22', :'$23']
123 @LOCAL_REGISTERS_SET = Set.new @LOCAL_REGISTERS
124 @REGISTER_LOCAL_BASE = 16
125 @NREGISTER_LOCALS = @LOCAL_REGISTERS.length
126 @RA_OFFSET = -@WORDSIZE
131 @SAVE_FRAME_REGISTERS = [:'$16', :'$17', :'$18', :'$19', :'$20',
132 :'$21', :'$22', :'$23', :'$28', :'$29',
134 @SAVED_FRAME_LAYOUT = {}
135 @SAVE_FRAME_REGISTERS.each_with_index { |r,i| @SAVED_FRAME_LAYOUT[r] = i }
136 @TEMPORARIES = [:'$8', :'$9', :'$10', :'$11',
137 :'$12', :'$13', :'$14', :'$15']
138 @function_end_label = nil
142 @output_file_suffix = '.s'
143 @saved_registers = []
145 :'bits-per-word' => '32',
146 :'bytes-per-word' => '4'
149 @features[:'byte-order'] = 'big-endian'
151 @features[:'byte-order'] = 'little-endian'
153 raise ArgumentError.new("#{self.class} does not support " +
154 "architecture #{@architecture}")
158 # Adds immediate to source and stores the result in target.
159 def addiu target, source, immediate, temporary = @TEMPORARY
160 if immediate >= -32768 && immediate < 32767
161 emit "addiu #{target}, #{source}, #{immediate}\n"
163 emit "lui #{target}, #{(immediate >> 16) & 0xffff}\n"
164 emit "ori #{target}, #{target}, #{immediate & 0xffff}\n"
166 addiu temporary, "$0", immediate
167 emit "addu #{target}, #{source}, #{temporary}\n"
171 # Return the offset from the frame base at which the nth argument is
177 # Returns an $fp-relative reference for the nth (0-based) argument.
179 offset_reference(arg_offset(n))
182 # Returns the register in which the nth (0-based) argument is stored, or
183 # nil if not stored in a register.
186 "$#{@REGISTER_ARG_BASE + n}"
192 def auto_bytes n, register
193 if n.kind_of? Integer
194 # Maintain stack alignment
195 n = (n + @STACK_ALIGNMENT - 1) / @STACK_ALIGNMENT * @STACK_ALIGNMENT
198 temporary = @TEMPORARIES.pop
200 load_value_into_register n, register
201 emit "addi #{register}, #{@STACK_ALIGNMENT - 1}\n"
202 emit "li #{temporary}, -#{@STACK_ALIGNMENT}\n"
203 emit "and #{register}, #{register}, #{temporary}\n"
204 emit "sub $sp, #{register}\n"
206 @TEMPORARIES.push temporary
209 emit "move #{register}, $sp\n" unless register == "$sp"
212 def auto_words n, register
213 if n.kind_of? Integer
214 auto_bytes n * @WORDSIZE, register
216 load_value_into_register n, register
217 if @STACK_ALIGNMENT_BITS > @WORDSIZE_BITS
218 bits = @STACK_ALIGNMENT_BITS - @WORDSIZE_BITS
219 emit "addi #{register}, #{(1 << bits) - 1}\n"
220 emit "srl #{register}, #{register}, #{bits}\n"
221 emit "sll #{register}, #{register}, #{@STACK_ALIGNMENT_BITS}\n"
223 emit "sll #{register}, #{register}, #{@WORDSIZE_BITS}\n"
225 emit "sub $sp, $sp, #{register}\n"
226 emit "move #{register}, $sp\n" unless register == "$sp"
230 # Begins a new block.
231 def begin_block *code
232 # If we are at top-level, create a frame
233 if @environment == @top_level
234 create_frame count_locals(code)
236 environment = Environment.new @environment
237 @environment = environment
240 # Emits function prologue and declare _formals_ as function arguments.
241 def begin_function formals, nlocals
242 if @environment != @top_level
243 raise "Cannot begin function when already in a function"
246 environment = Environment.new @environment
248 formals.each {|x| environment.add_arg x, arg_offset(environment.args)}
249 @environment = environment
250 @function_end_label = gensym
251 emit_function_prologue formals, nlocals
254 # Defines a byte with the given value.
256 emit ".byte #{value}\n"
261 # Grow the stack frame, subject to 3 conditions:
262 # 1. There must be enough space to hold all arguments
263 # 2. $sp must remain a multiple of 8
264 # 3. We must provide space for at least 4 words
265 increment = ([args.length, 4].max * @WORDSIZE + 7) / 8 * 8
268 # Put arguments in the right places
270 while n < args.length
271 if n < @NREGISTER_ARGS
272 # Put arguments up to @NREGISTER_ARGS in registers
273 load_value_into_register args[n], arg_register(n)
275 # Put other arguments on the stack
276 load_value_into_register args[n], @TEMPORARY
277 emit "sw #{@TEMPORARY}, #{n * @WORDSIZE}($sp)\n"
282 # Load function address
284 if @imports.has_key? func
285 # Load address from global offset table
286 emit "lw #{@FUNCTION}, %call16(#{func})(#{@GOT})\n"
288 # Assume label defined in this module
289 emit "lui #{@FUNCTION}, %hi(#{func})\n"
290 emit "addiu #{@FUNCTION}, %lo(#{func})\n"
294 load_value_into_register func, "#{@FUNCTION}"
298 emit "jalr #{@FUNCTION}\n"
302 # Restore original stack frame
303 grow_stack -increment
306 emit "lw #{@GOT}, #{@GP_OFFSET}($fp)\n"
314 # Starts a conditional using the specified branch instruction
315 # after the comparison.
316 def common_if comp, x, y = nil
317 temporaries = @TEMPORARIES.dup
318 xreg = load_value x, temporaries[0]
319 temporaries.delete xreg
320 yreg = load_value y, temporaries[0]
321 temporaries.delete yreg
323 falselabel = @environment.gensym
324 @if_labels.push falselabel
328 emit "bne #{xreg}, #{yreg}, #{falselabel}\n"
330 emit "slt #{@TEMPORARY}, #{xreg}, #{yreg}\n"
331 emit "bne #{@TEMPORARY}, $0, #{falselabel}\n"
333 emit "slt #{@TEMPORARY}, #{yreg}, #{xreg}\n"
334 emit "beq #{@TEMPORARY}, $0, #{falselabel}\n"
336 emit "slt #{@TEMPORARY}, #{yreg}, #{xreg}\n"
337 emit "bne #{@TEMPORARY}, $0, #{falselabel}\n"
339 emit "slt #{@TEMPORARY}, #{xreg}, #{yreg}\n"
340 emit "beq #{@TEMPORARY}, $0, #{falselabel}\n"
342 emit "beq #{xreg}, #{yreg}, #{falselabel}\n"
344 raise "Unknown conditional: #{comp}"
349 # Creates an activation frame which can store nlocals local variables.
350 def create_frame nlocals
351 @frame_size = @INITIAL_FRAME_SIZE
353 @frame_size = @frame_size + (nlocals * @WORDSIZE + 7) / 8 * 8
355 grow_stack @frame_size
356 @saved_registers = []
359 def emit_align alignment
360 emit ".align #{alignment}\n"
363 # Emits function prologue.
364 def emit_function_prologue formals = [], nlocals = 0
365 # Calculate new value for $gp
366 emit "lui #{@GOT}, %hi(_gp_disp)\n"
367 emit "addiu #{@GOT}, %lo(_gp_disp)\n"
368 emit "addu #{@GOT}, #{@GOT}, #{@FUNCTION}\n"
372 # Save return address
373 emit "sw $31, #{@frame_size - @WORDSIZE}($sp)\n"
376 emit "sw #{@GOT}, #{@frame_size - 2 * @WORDSIZE}($sp)\n"
379 emit "sw $fp, #{@frame_size - 3 * @WORDSIZE}($sp)\n"
381 # Point fp at where sp was before we created the frame
382 addiu "$fp", "$sp", @frame_size
384 # Save parameters 0 .. 3 in the stack space that the caller
385 # should have allocated for them.
386 [@NREGISTER_ARGS, formals.length].min.times do |n|
387 ref = offset_reference(@environment[formals[n]])
388 emit "sw $#{n + @REGISTER_ARG_BASE}, #{ref}\n"
392 # Loads a word into a register.
393 def emit_load_word register, base, offset
394 emit "lw #{register}, #{offset * @WORDSIZE}(#{base})\n"
397 # Stores the value of a register in memory.
398 def emit_store_word register, base, offset
399 emit "sw #{register}, #{offset * @WORDSIZE}(#{base})\n"
402 # Ends a function body.
404 if @environment == @top_level
405 raise "Cannot end function when not in a function"
408 label @function_end_label
409 # Restore saved locals
410 [@NREGISTER_LOCALS, @environment.locals].min.times do |n|
411 emit "lw #{local_register n}, #{local_reference n}\n"
413 @saved_registers = []
414 # Load return address
415 emit "lw $31, #{@RA_OFFSET}($fp)\n"
416 # Restore stack pointer
417 emit "move $sp, $fp\n"
418 # Restore frame pointer
419 emit "lw $fp, #{@FP_OFFSET}($fp)\n"
424 @function_end_label = nil
425 @environment = @top_level
428 # Ends the current block.
430 # If we are returning to top level, restore stack pointer
431 if @environment.parent == @top_level
432 grow_stack -@frame_size
433 @saved_registers = []
436 # Restore old value of @environment
437 @environment = @environment.parent
440 # Ends a conditional.
442 label = @if_labels.pop
446 # Evaluates the binary operation expr and store the result in register.
447 def eval_binop expr, register
448 temporaries = @TEMPORARIES.dup
449 x = load_value expr[1], temporaries[0]
451 y = load_value expr[2], temporaries[0]
456 emit "srav #{register}, #{x}, #{y}\n"
458 emit "srlv #{register}, #{x}, #{y}\n"
460 emit "div $0, #{x}, #{y}\n"
461 emit "mflo #{register}\n"
463 emit "div $0, #{x}, #{y}\n"
464 emit "mfhi #{register}\n"
466 emit "mult #{x}, #{y}\n"
467 emit "mflo #{register}\n"
469 emit "subu #{@TEMPORARY}, $0, #{y}\n"
470 emit "srlv #{@TEMPORARY}, #{x}, #{@TEMPORARY}\n"
471 emit "sllv #{register}, #{x}, #{y}\n"
472 emit "or #{register}, #{register}, #{@TEMPORARY}\n"
474 emit "subu #{@TEMPORARY}, $0, #{y}\n"
475 emit "sllv #{@TEMPORARY}, #{x}, #{@TEMPORARY}\n"
476 emit "srlv #{register}, #{x}, #{y}\n"
477 emit "or #{register}, #{register}, #{@TEMPORARY}\n"
479 emit "sllv #{register}, #{x}, #{y}\n"
481 emit "srlv #{register}, #{x}, #{y}\n"
483 emit "#{expr[0]} #{register}, #{x}, #{y}\n"
487 # Evaluates the expression expr and store the result in register.
488 def eval_expr expr, register
491 load_value_into_register expr[0], register
493 # Evaluate expression
497 auto_bytes expr[1], register
499 auto_words expr[1], register
502 emit "move #{register}, #{@RETURN}\n" if register != @RETURN
504 get_byte expr[1], expr[2], register
506 get_word expr[1], expr[2], register
508 eval_binop [:nor, 0, expr[1]], register
511 eval_binop expr, register
513 raise "Not a magic word: #{op}"
519 # Exports symbols from the current section.
521 symbols.each { |sym| emit ".globl #{sym}\n" }
524 # Loads byte from _base_ + _offset_ into _register_.
525 def get_byte base, offset, register
526 # If base is an integer, but offset isn't, swap them
527 if !integer?(offset) && integer?(base)
528 base, offset = [offset, base]
532 base_reg = load_value base
533 emit "lb #{register}, #{offset}(#{base_reg})\n"
535 eval_binop [:add, base, offset], @TEMPORARY
536 emit "lb #{register}, 0(#{@TEMPORARY})\n"
540 # Loads word from _base_ + _offset_ * _@WORDSIZE_ into _register_.
541 def get_word base, offset, register
543 base_reg = load_value base
544 emit "lw #{register}, #{offset * @WORDSIZE}(#{base_reg})\n"
546 offset_reg = @TEMPORARIES.pop
548 load_value_into_register offset, offset_reg
549 base_reg = load_value base
550 emit "sll #{offset_reg}, #{offset_reg}, 2\n" # multiply by @WORDSIZE
551 emit "add #{@TEMPORARY}, #{base_reg}, #{offset_reg}\n"
552 emit "lw #{register}, 0(#{@TEMPORARY})\n"
554 @TEMPORARIES.push offset_reg
559 # Jumps to an address.
562 emit "j #{address}\n"
564 register = load_value address, @TEMPORARY
565 emit "jr #{register}\n"
570 # Grows the stack by n bytes.
572 addiu "$sp", "$sp", -n
575 # Starts the false path of a conditional.
577 newlabel = @environment.gensym
578 emit "j #{newlabel}\n"
580 label = @if_labels.pop
582 @if_labels.push newlabel
585 # Tests if x is equal to y
587 common_if :ifeq, x, y
590 # Tests if x is greater than or equal to y
592 common_if :ifge, x, y
595 # Tests if x is strictly greater than y
597 common_if :ifgt, x, y
600 # Tests if x is less than or equal to y
602 common_if :ifle, x, y
605 # Tests if x is strictly less than y
607 common_if :iflt, x, y
610 # Tests if x different from y
612 common_if :ifne, x, y
615 # Imports labels into the current section.
617 # Record imported labels in @imports
618 symbols.each { |sym| @imports[sym] = sym }
626 # Introduces a new local variable.
627 def let symbol, *expr
628 n = @environment.locals
629 register = local_register n
630 ref = local_reference n
632 # We will use a register to store the value
633 @environment.add_local symbol, register
634 # Save current value of register
635 emit "sw #{register}, #{ref}\n"
636 @saved_registers << register
638 eval_expr expr, register
640 # We will use the stack to store the value
641 @environment.add_local symbol, local_offset(n)
642 eval_expr expr, @TEMPORARY
643 emit "sw #{@TEMPORARY}, #{ref}\n"
647 # Loads the value at the given address.
648 def load_at address, register = @TEMPORARY
649 load_value_into_register address, register
650 emit "lw #{register}, 0(#{register})\n"
654 # Loads a value into a register.
655 # Returns the name of the register.
656 # If the value was already in a register, the name of that
657 # register is returned.
658 # Else, the value is loaded into a register and the name of
659 # that register is returned. The register to use in that case
660 # may be specified using the optional second argument.
661 def load_value x, register = @TEMPORARY
663 x = substitute_number x[1]
669 addiu register, "$0", x
672 binding = @environment[x]
674 # Value is already in a register. Return register name.
676 elsif binding.kind_of? Integer
677 # Load value from memory.
678 emit "lw #{register}, #{offset_reference binding}\n"
682 emit "lui #{register}, %hi(#{x})\n"
683 emit "addiu #{register}, %lo(#{x})\n"
687 load_at x[1], register
689 raise "Don't know how to load #{x.inspect}"
693 # Loads a value into a specific register.
694 def load_value_into_register x, register
695 reg = load_value x, register
697 emit "move #{register}, #{reg}\n"
701 # Returns the offset from the frame base at which the nth local is stored.
702 # For register locals this is the offset at which the saved
703 # value (from the calling function) is stored.
708 # Returns an $sp-relative reference for the nth (0-based) local.
709 def local_reference n
710 offset_reference(local_offset(n))
713 # Returns the register in which the nth local (0-based) is stored, or
714 # nil if not stored in a register.
719 # Computes the maximum number of locals that would fit in the current
722 # + 1, because the initial frame size has room for 1 local
723 (@frame_size - @INITIAL_FRAME_SIZE) / @WORDSIZE + 1
726 # Given an offset relative to the base of the frame, returns
727 # an reference to that memory location.
728 def offset_reference offset
732 # Returns true if the nth (0-based) local is stored in a register.
733 def register_local? n
734 n < @NREGISTER_LOCALS
737 # Returns from a function.
739 # _words_ may contain an expression to be evaluated. The result
740 # of the evaluation is returned from the function.
742 # Compute return value and store it in @RETURN
743 eval_expr(words, @RETURN) unless words.empty?
745 goto @function_end_label
748 # Saves the current frame at the given location.
749 def save_frame location
750 load_value_into_register location, @TEMPORARY
751 @SAVE_FRAME_REGISTERS.each_with_index do |register,i|
752 emit "sw #{register}, #{i * @WORDSIZE}(#{@TEMPORARY})\n"
756 # Sets a variable to the result of evaluating an expression.
757 def set symbol, *expr
759 eval_expr expr, @RETURN
760 load_value_into_register symbol.to_s[1..-1].to_sym, @TEMPORARY
761 emit "sw #{@RETURN}, 0(#{@TEMPORARY})\n"
763 x = @environment[symbol]
765 raise "Cannot change value of constant #{symbol}"
769 # Should be an integer.
770 eval_expr expr, @TEMPORARY
771 emit "sw #{@TEMPORARY}, #{offset_reference x}\n"
776 # Sets the byte at _base_ + _offset_ to _value_.
777 def set_byte base, offset, value
778 # If base is an integer, but offset isn't, swap them
779 if !integer?(offset) && integer?(base)
780 base, offset = [offset, base]
783 value_reg = @TEMPORARIES.pop
784 load_value_into_register value, value_reg
787 base_reg = load_value base
788 emit "sb #{value_reg}, #{offset}(#{base_reg})\n"
790 eval_binop [:add, base, offset], @TEMPORARY
791 emit "sb #{value_reg}, 0(#{@TEMPORARY})\n"
794 @TEMPORARIES.push value_reg
798 # Sets the word at _base_ + _offset_ * +@WORDSIZE+ to _value_.
799 def set_word base, offset, value
800 value_reg = @TEMPORARIES.pop
801 load_value_into_register value, value_reg
804 base_reg = load_value base
805 emit "sw #{value_reg}, #{offset * @WORDSIZE}(#{base_reg})\n"
807 offset_reg = @TEMPORARIES.pop
809 load_value_into_register offset, offset_reg
810 base_reg = load_value base
811 emit "sll #{offset_reg}, #{offset_reg}, 2\n"
812 emit "add #{@TEMPORARY}, #{base_reg}, #{offset_reg}\n"
813 emit "sw #{value_reg}, 0(#{@TEMPORARY})\n"
815 @TEMPORARIES.push offset_reg
819 @TEMPORARIES.push value_reg
823 # Defines a string with the given value.
826 value.each_byte do |b|
829 elsif b >= 32 && b < 127 && b != 34
832 code << sprintf("\\%03o", b)
835 emit ".ascii \"#{code}\"\n"
838 # Calls a function, re-using the current call frame if possible.
839 def tail_call func, *args
840 # Compute number of stack arguments
841 nstackargs = number_of_stack_arguments args.length
842 # If we need more stack arguments than we have now,
843 # perform a normal call and return
844 if nstackargs > number_of_stack_arguments(@environment.args)
845 emit "# Not enough space for proper tail call; using regular call\n"
846 ret :call, func, *args
849 # Back up any stack arguments we will need after we overwrite them
850 temporaries = @TEMPORARIES.dup
851 nlocals = @environment.locals
852 (@NREGISTER_ARGS...args.length).each do |i|
853 x = @environment[args[i]]
854 if integer?(x) && x < arg_offset(i)
855 # args[i] is in a location that will have been overwritten by the
856 # time we get around to passing argument i to the called function.
857 # Make a backup of the value before we overwrite it.
858 if temporaries.empty?
859 # Oh dear, we're out of temporaries.
860 # Store the value in the current stack frame, extending it
862 if nlocals >= max_locals
865 reg = load_value args[i]
866 emit "sw #{reg}, #{local_reference nlocals}\n"
867 args[i] = [:local, nlocals]
868 nlocals = nlocals + 1
870 # Load the argument into a temporary
871 reg = temporaries.shift
872 load_value_into_register args[i], reg
873 # Update args[i] so we know how to get to it later
874 args[i] = [:reg, reg]
879 # Set stack arguments
880 (@NREGISTER_ARGS...args.length).each do |i|
885 if arg.kind_of? Array
886 # Special cases, created above
891 emit "lw #{reg}, #{local_reference arg[1]}\n"
894 load_value_into_register arg, reg
897 # Store value in designated place
898 emit "sw #{reg}, #{arg_reference i}\n"
901 # Set register arguments
902 [@NREGISTER_ARGS,args.length].min.times do |i|
904 load_value_into_register args[i], reg
907 # Load function address
909 if @imports.has_key? func
910 # Load address from global offset table
911 emit "lw #{@FUNCTION}, %call16(#{func})(#{@GOT})\n"
913 # Assume label defined in this module
914 emit "lui #{@FUNCTION}, %hi(#{func})\n"
915 emit "addiu #{@FUNCTION}, %lo(#{func})\n"
919 load_value_into_register func, "#{@FUNCTION}"
922 # Restore saved registers
923 [@NREGISTER_LOCALS, @environment.locals].min.times do |n|
924 emit "lw #{local_register n}, #{local_reference n}\n"
927 # Restore return address
928 emit "lw $31, #{@RA_OFFSET}($fp)\n"
930 # Restore stack pointer
931 emit "move $sp, $fp\n"
933 # Restore frame pointer
934 emit "lw $fp, #{@FP_OFFSET}($fp)\n"
937 emit "jr #{@FUNCTION}\n"
942 # Defines a word with the given value
944 emit ".int #{value}\n"
947 # Write generated code to the given IO object.
950 @sections.each do |section,code|
952 io.puts ".section #{section.to_s}"
961 # Register class for big endian MIPS
962 Voodoo::CodeGenerator.register_generator MIPSGasGenerator,
963 :architecture => :mips,
967 # Register class for little endian MIPS
968 Voodoo::CodeGenerator.register_generator MIPSGasGenerator,
969 :architecture => :mipsel,