lib/voodoo/generators/mips_gas_generator.rb

   1 require 'voodoo/generators/common_code_generator'
   2
   3 module Voodoo
   4   # = MIPS GNU Assembler Code Generator
   5   #
   6   # The MIPS 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 $4 through $7.
  12   # Any additional arguments are passed on the stack, starting at
  13   # $sp + 16. Words $sp through $sp + 12 will be available for the called
  14   # function to use. $sp will always be a multiple of 8.
  15   #
  16   # The return address for the called function is passed in $31.
  17   #
  18   # When performing a position-independent call, the address of the called
  19   # function is passed in $25.
  20   #
  21   # The called function will store its return value in $2.
  22   #
  23   # The called function is required to preserve the values of registers
  24   # $16 through $23 and register $30.
  25   #
  26   # This calling convention is compatible with the System V ELF ABI.
  27   #
  28   # == Call Frames
  29   #
  30   # Call frames have the following layout:
  31   #
  32   # When a function is called, it receives a stack frame that looks like
  33   # the following:
  34   #
  35   #   :
  36   #   old frame
  37   #   argn
  38   #   :
  39   #   arg4
  40   #   empty3
  41   #   empty2
  42   #   empty1
  43   #   empty0    <-- $sp points here
  44   #
  45   # The function prologue of functions generated by this code generator
  46   # creates activation frames that look as follows:
  47   #
  48   # :
  49   # old frame
  50   # argn
  51   # :
  52   # arg4
  53   # arg3
  54   # arg2
  55   # arg1
  56   # arg0       <-- $fp points here
  57   # return address
  58   # pointer to Global Offset Table
  59   # saved $fp
  60   # local0
  61   # :
  62   # local7
  63   # local8
  64   # :
  65   # localn
  66   # padding    <-- $sp points here
  67   #
  68   # In words:
  69   #
  70   # The four empty slots provided by the caller are used to store
  71   # arguments 0 through 3 (originally passed in $4 through $7),
  72   # if necessary.
  73   #
  74   # The stack frame created below the four slots provided by the caller
  75   # contains the following data, in order:
  76   #
  77   # - Saved return address (originally passed in $31), if necessary.
  78   #
  79   # - Saved pointer to global offset table (computed from $25), if necessary.
  80   #
  81   # - Saved value of $fp, if necessary.
  82   #
  83   # - Saved values of caller's locals 0 through 7
  84   #   (originally in $16 through $23), if necessary.
  85   #
  86   # - Values of our locals > 8, if necessary.
  87   #
  88   # - Padding to align $sp on a multiple of 8, if necessary.
  89   #
  90   #
  91   # In accordance with the System V ELF ABI for MIPS, the pointer to
  92   # the global offset table is calculated as follows:
  93   #
  94   # $gp = _gp_disp + $25
  95   #
  96   # where $gp is the register to store the pointer, $25 is the register
  97   # holding the address of the called function, and _gp_disp is the
  98   # offset between the beginning of the function and the global offset table.
  99   #
 100   class MIPSGasGenerator < CommonCodeGenerator
 101     def initialize params
 102       @WORDSIZE = 4
 103       @CODE_ALIGNMENT = 0
 104       @DATA_ALIGNMENT = @WORDSIZE
 105       @FP_OFFSET = -3 * @WORDSIZE
 106       @FUNCTION_ALIGNMENT = @WORDSIZE
 107       @GP_OFFSET = -2 * @WORDSIZE
 108       @INITIAL_FRAME_SIZE = 4 * @WORDSIZE
 109       @REGISTER_ARG_BASE = 4
 110       @NREGISTER_ARGS = 4
 111       @REGISTER_LOCAL_BASE = 16
 112       @NREGISTER_LOCALS = 8
 113       @RA_OFFSET = -@WORDSIZE
 114       @RETURN = :'$2'
 115       @TEMPORARY = :'$1'
 116       @FUNCTION = :'$25'
 117       @GOT = :'$28'
 118       @TEMPORARIES = [:'$8', :'$9', :'$10', :'$11',
 119                       :'$12', :'$13', :'$14', :'$15']
 120       @function_end_label = nil
 121       @imports = {}
 122       @if_labels = []
 123       super params
 124       @output_file_suffix = '.s'
 125       @features.merge! \
 126         :'bits-per-word' => '32',
 127         :'bytes-per-word' => '4'
 128       case @architecture
 129       when :mips
 130         @features[:'byte-order'] = 'big-endian'
 131       when :mipsel
 132         @features[:'byte-order'] = 'little-endian'
 133       else
 134         raise ArgumentError.new("#{self.class} does not support " +
 135                                 "architecture #{@architecture}")
 136       end
 137     end
 138
 139     # Adds immediate to source and stores the result in target.
 140     def addiu target, source, immediate, temporary = @TEMPORARY
 141       if immediate >= -32768 && immediate < 32767
 142         emit "addiu #{target}, #{source}, #{immediate}\n"
 143       elsif source == "$0"
 144         emit "lui #{target}, #{(immediate >> 16) & 0xffff}\n"
 145         emit "ori #{target}, #{target}, #{immediate & 0xffff}\n"
 146       else
 147         addiu temporary, "$0", immediate
 148         emit "addu #{target}, #{source}, #{temporary}\n"
 149       end
 150     end
 151
 152     def align alignment = nil
 153       unless alignment
 154         # Get default alignment
 155         case @section
 156         when :code
 157           alignment = @CODE_ALIGNMENT
 158         when :data
 159           alignment = @DATA_ALIGNMENT
 160         when :function
 161           alignment = @FUNCTION_ALIGNMENT
 162         else
 163           # Use data alignment as default
 164           alignment = @DATA_ALIGNMENT
 165         end
 166       end
 167       emit ".align #{alignment}\n" unless alignment == 0
 168     end
 169
 170     # Return the offset from the frame base at which the nth argument is
 171     # stored.
 172     def arg_offset n
 173       n * @WORDSIZE
 174     end
 175
 176     # Return an $fp-relative reference for the nth (0-based) argument
 177     def arg_reference n
 178       offset_reference(arg_offset(n))
 179     end
 180
 181     # Return the register in which the nth (0-based) argument is stored, or
 182     # nil if not stored in a register
 183     def arg_register n
 184       if register_arg? n
 185         "$#{@REGISTER_ARG_BASE + n}"
 186       else
 187         nil
 188       end
 189     end
 190
 191     # Test if op is a binary operation
 192     def assymetric_binop? op
 193       [:asr, :bsr, :div, :mod, :rol, :ror, :shl, :shr, :sub].member?(op)
 194     end
 195
 196     # Test if a value is an at-expression
 197     def at_expr? value
 198       value.respond_to?(:[]) && value[0] == :'@'
 199     end
 200
 201     def auto_bytes n, register
 202       # Maintain stack pointer at a multiple of 8 bytes.
 203       n = (n + 7) / 8 * 8
 204       grow_stack n
 205       emit "move #{register}, $sp\n" unless register == "$sp"
 206     end
 207
 208     def auto_words n, register
 209       auto_bytes n * @WORDSIZE, register
 210     end
 211
 212     # Begins a new block.
 213     def begin_block *code
 214       emit "# begin block\n"
 215       # If we are at top-level, create a frame
 216       if @environment == @top_level
 217         create_frame count_locals(code)
 218       end
 219       environment = Environment.new @environment
 220       @environment = environment
 221     end
 222
 223     # Emit function prologue and declare _formals_ as function arguments
 224     def begin_function formals, nlocals
 225       if @environment != @top_level
 226         raise "Cannot begin function when already in a function"
 227       end
 228
 229       environment = Environment.new @environment
 230       @frame_size = 0
 231       formals.each {|x| environment.add_arg x, arg_offset(environment.args)}
 232       @environment = environment
 233       @function_end_label = gensym
 234       emit_function_prologue formals, nlocals
 235     end
 236
 237     # Test if op is a binary operation
 238     def binop? op
 239       assymetric_binop?(op) || symmetric_binop?(op)
 240     end
 241
 242     # Define a byte with the given value
 243     def byte value
 244       emit ".byte #{value}\n"
 245     end
 246
 247     # Call a function.
 248     def call func, *args
 249       # Grow the stack frame, subject to 3 conditions:
 250       # 1. There must be enough space to hold all arguments
 251       # 2. $sp must remain a multiple of 8
 252       # 3. We must provide space for at least 4 words
 253       increment = ([args.length, 4].max * @WORDSIZE + 7) / 8 * 8
 254       grow_stack increment
 255
 256       # Put arguments in the right places
 257       n = 0
 258       while n < args.length
 259         if n < @NREGISTER_ARGS
 260           # Put arguments up to @NREGISTER_ARGS in registers
 261           load_value_into_register args[n], arg_register(n)
 262         else
 263           # Put other arguments on the stack
 264           load_value_into_register args[n], @TEMPORARY
 265           emit "sw #{@TEMPORARY}, #{n * @WORDSIZE}($sp)\n"
 266         end
 267         n = n + 1
 268       end
 269
 270       # Load function address
 271       if global? func
 272         if @imports.has_key? func
 273           # Load address from global offset table
 274           emit "lw #{@FUNCTION}, %call16(#{func})(#{@GOT})\n"
 275         else
 276           # Assume label defined in this module
 277           emit "lui #{@FUNCTION}, %hi(#{func})\n"
 278           emit "addiu #{@FUNCTION}, %lo(#{func})\n"
 279         end
 280       else
 281         # Load address
 282         load_value_into_register func, "#{@FUNCTION}"
 283       end
 284
 285       # Perform call
 286       emit "jalr #{@FUNCTION}\n"
 287       # brach delay slot
 288       emit "nop\n"
 289
 290       # Restore original stack frame
 291       grow_stack -increment
 292
 293       # restore gp
 294       emit "lw #{@GOT}, #{@GP_OFFSET}($fp)\n"
 295     end
 296
 297     # Emits a comment.
 298     def comment text
 299       emit "# #{text}\n"
 300     end
 301
 302     # Start a conditional using the specified branch instruction
 303     # after the comparison.
 304     def common_if comp, x, y = nil
 305       emit "# #{comp} #{x} #{y}\n"
 306
 307       temporaries = @TEMPORARIES.dup
 308       xreg = load_value x, temporaries[0]
 309       temporaries.delete xreg
 310       yreg = load_value y, temporaries[0]
 311       temporaries.delete yreg
 312
 313       falselabel = @environment.gensym
 314       @if_labels.push falselabel
 315
 316       case comp
 317       when :ifeq
 318         emit "bne #{xreg}, #{yreg}, #{falselabel}\n"
 319       when :ifge
 320         emit "slt #{@TEMPORARY}, #{xreg}, #{yreg}\n"
 321         emit "bne #{@TEMPORARY}, $0, #{falselabel}\n"
 322       when :ifgt
 323         emit "slt #{@TEMPORARY}, #{yreg}, #{xreg}\n"
 324         emit "beq #{@TEMPORARY}, $0, #{falselabel}\n"
 325       when :ifle
 326         emit "slt #{@TEMPORARY}, #{yreg}, #{xreg}\n"
 327         emit "bne #{@TEMPORARY}, $0, #{falselabel}\n"
 328       when :iflt
 329         emit "slt #{@TEMPORARY}, #{xreg}, #{yreg}\n"
 330         emit "beq #{@TEMPORARY}, $0, #{falselabel}\n"
 331       when :ifne
 332         emit "beq #{xreg}, #{yreg}, #{falselabel}\n"
 333       else
 334         raise "Unknown conditional: #{comp}"
 335       end
 336       emit "nop\n"
 337     end
 338
 339     # Creates an activation frame which can store nlocals local variables
 340     def create_frame nlocals
 341       @frame_size = @INITIAL_FRAME_SIZE
 342       if nlocals > 0
 343         @frame_size = @frame_size + (nlocals * @WORDSIZE + 7) / 8 * 8
 344       end
 345       grow_stack @frame_size
 346     end
 347
 348     # Emit function prologue.
 349     def emit_function_prologue formals = [], nlocals = 0
 350       # Calculate new value for $gp
 351       emit "lui #{@GOT}, %hi(_gp_disp)\n"
 352       emit "addiu #{@GOT}, %lo(_gp_disp)\n"
 353       emit "addu #{@GOT}, #{@GOT}, #{@FUNCTION}\n"
 354
 355       create_frame nlocals
 356
 357       # Save return address
 358       emit "sw $31, #{@frame_size - @WORDSIZE}($sp)\n"
 359
 360       # Save gp
 361       emit "sw #{@GOT}, #{@frame_size - 2 * @WORDSIZE}($sp)\n"
 362
 363       # Save fp
 364       emit "sw $fp, #{@frame_size - 3 * @WORDSIZE}($sp)\n"
 365
 366       # Point fp at where sp was before we created the frame
 367       addiu "$fp", "$sp", @frame_size
 368
 369       # Save parameters 0 .. 3 in the stack space that the caller
 370       # should have allocated for them.
 371       [@NREGISTER_ARGS, formals.length].min.times do |n|
 372         ref = offset_reference(@environment[formals[n]])
 373         emit "sw $#{n + @REGISTER_ARG_BASE}, #{ref}\n"
 374       end
 375     end
 376
 377     # End a function body
 378     def end_function
 379       if @environment == @top_level
 380         raise "Cannot end function when not in a function"
 381       end
 382
 383       label @function_end_label
 384       # Restore saved locals
 385       [@NREGISTER_LOCALS, @environment.locals].min.times do |n|
 386         emit "lw #{local_register n}, #{local_reference n}\n"
 387       end
 388       # Load return address
 389       emit "lw $31, #{@RA_OFFSET}($fp)\n"
 390       # Restore stack pointer
 391       emit "move $sp, $fp\n"
 392       # Restore frame pointer
 393       emit "lw $fp, #{@FP_OFFSET}($fp)\n"
 394       # Return
 395       emit "jr $31\n"
 396       emit "nop\n"
 397
 398       emit "# end function\n\n"
 399
 400       @function_end_label = nil
 401       @environment = @top_level
 402     end
 403
 404     # Ends the current block.
 405     def end_block
 406       emit "# end block\n"
 407
 408       # If we are returning to top level, restore stack pointer
 409       if @environment.parent == @top_level
 410         grow_stack -@frame_size
 411       end
 412
 413       # Restore old value of @environment
 414       @environment = @environment.parent
 415     end
 416
 417     # End a conditional.
 418     def end_if
 419       label = @if_labels.pop
 420       emit "#{label}:\n"
 421     end
 422
 423     # Evaluate the binary operation expr and store the result in register
 424     def eval_binop expr, register
 425       temporaries = @TEMPORARIES.dup
 426       x = load_value expr[1], temporaries[0]
 427       temporaries.delete x
 428       y = load_value expr[2], temporaries[0]
 429       temporaries.delete y
 430
 431       case expr[0]
 432       when :asr
 433         emit "srav #{register}, #{x}, #{y}\n"
 434       when :bsr
 435         emit "srlv #{register}, #{x}, #{y}\n"
 436       when :div
 437         emit "div $0, #{x}, #{y}\n"
 438         emit "mflo #{register}\n"
 439       when :mod
 440         emit "div $0, #{x}, #{y}\n"
 441         emit "mfhi #{register}\n"
 442       when :mul
 443         emit "mult #{x}, #{y}\n"
 444         emit "mflo #{register}\n"
 445       when :rol
 446         emit "subu #{@TEMPORARY}, $0, #{y}\n"
 447         emit "srlv #{@TEMPORARY}, #{x}, #{@TEMPORARY}\n"
 448         emit "sllv #{register}, #{x}, #{y}\n"
 449         emit "or #{register}, #{register}, #{@TEMPORARY}\n"
 450       when :ror
 451         emit "subu #{@TEMPORARY}, $0, #{y}\n"
 452         emit "sllv #{@TEMPORARY}, #{x}, #{@TEMPORARY}\n"
 453         emit "srlv #{register}, #{x}, #{y}\n"
 454         emit "or #{register}, #{register}, #{@TEMPORARY}\n"
 455       when :shl
 456         emit "sllv #{register}, #{x}, #{y}\n"
 457       when :shr
 458         emit "srlv #{register}, #{x}, #{y}\n"
 459       else
 460         emit "#{expr[0]} #{register}, #{x}, #{y}\n"
 461       end
 462     end
 463
 464     # Evaluate the expression expr and store the result in register
 465     def eval_expr expr, register
 466       if expr.length == 1
 467         # Load value
 468         load_value_into_register expr[0], register
 469       else
 470         # Evaluate expression
 471         op = expr[0]
 472         case op
 473         when :'auto-bytes'
 474           auto_bytes expr[1], register
 475         when :'auto-words'
 476           auto_words expr[1], register
 477         when :call
 478           call *expr[1..-1]
 479           emit "move #{register}, #{@RETURN}\n" if register != @RETURN
 480         when :'get-byte'
 481           get_byte expr[1], expr[2], register
 482         when :'get-word'
 483           get_word expr[1], expr[2], register
 484         when :not
 485             eval_binop [:nor, 0, expr[1]], register
 486         else
 487           if binop? op
 488             eval_binop expr, register
 489           else
 490             raise "Not a magic word: #{op}"
 491           end
 492         end
 493       end
 494     end
 495
 496     # Export symbols from the current section
 497     def export *symbols
 498       symbols.each { |sym| emit ".globl #{sym}\n" }
 499     end
 500
 501     # Load byte from _base_ + _offset_ into _register_
 502     def get_byte base, offset, register
 503       # If base is an integer, but offset isn't, swap them
 504       if !integer?(offset) && integer?(base)
 505         base, offset = [offset, base]
 506       end
 507
 508       if integer? offset
 509         base_reg = load_value base
 510         emit "lb #{register}, #{offset}(#{base_reg})\n"
 511       else
 512         eval_binop [:add, base, offset], @TEMPORARY
 513         emit "lb #{register}, 0(#{@TEMPORARY})\n"
 514       end
 515     end
 516
 517     # Load word from _base_ + _offset_ * _@WORDSIZE_ into _register_
 518     def get_word base, offset, register
 519       if integer? offset
 520         base_reg = load_value base
 521         emit "lw #{register}, #{offset * @WORDSIZE}(#{base_reg})\n"
 522       else
 523         offset_reg = @TEMPORARIES.pop
 524         begin
 525           load_value_into_register offset, offset_reg
 526           base_reg = load_value base
 527           emit "sll #{offset_reg}, #{offset_reg}, 2\n" # multiply by @WORDSIZE
 528           emit "add #{@TEMPORARY}, #{base_reg}, #{offset_reg}\n"
 529           emit "lw #{register}, 0(#{@TEMPORARY})\n"
 530         ensure
 531           @TEMPORARIES.push offset_reg
 532         end
 533       end
 534     end
 535
 536     # Test if a symbol refers to a global
 537     def global? symbol
 538       symbol?(symbol) && @environment[symbol] == nil
 539     end
 540
 541     # Jump to a label.
 542     def goto label
 543       emit "j #{label}\n"
 544       emit "nop\n"
 545     end
 546
 547     # Grows the stack by n bytes.
 548     def grow_stack n
 549       addiu "$sp", "$sp", -n
 550     end
 551
 552     # Start the false path of a conditional.
 553     def ifelse
 554       emit "# else\n"
 555       newlabel = @environment.gensym
 556       emit "j #{newlabel}\n"
 557       emit "nop\n"
 558       label = @if_labels.pop
 559       emit "#{label}:\n"
 560       @if_labels.push newlabel
 561     end
 562
 563     # Test if x is equal to y
 564     def ifeq x, y
 565       common_if :ifeq, x, y
 566     end
 567
 568     # Test if x is greater than or equal to y
 569     def ifge x, y
 570       common_if :ifge, x, y
 571     end
 572
 573     # Test if x is strictly greater than y
 574     def ifgt x, y
 575       common_if :ifgt, x, y
 576     end
 577
 578     # Test if x is less than or equal to y
 579     def ifle x, y
 580       common_if :ifle, x, y
 581     end
 582
 583     # Test if x is strictly less than y
 584     def iflt x, y
 585       common_if :iflt, x, y
 586     end
 587
 588     # Test if x different from y
 589     def ifne x, y
 590       common_if :ifne, x, y
 591     end
 592
 593     # Import labels into the current section
 594     def import *symbols
 595       # Record imported labels in @imports
 596       symbols.each { |sym| @imports[sym] = sym }
 597     end
 598
 599     # Test if a value is an integer
 600     def integer? value
 601       value.kind_of? Integer
 602     end
 603
 604     # Emit a label
 605     def label name
 606       emit "#{name}:\n"
 607     end
 608
 609     # Introduces a new local variable.
 610     def let symbol, *expr
 611       emit "# let #{symbol} #{expr.join ' '}\n"
 612       n = @environment.locals
 613       register = local_register n
 614       ref = local_reference n
 615       if register
 616         # We will use a register to store the value
 617         @environment.add_local symbol, register
 618         # Save current value of register
 619         emit "sw #{register}, #{ref}\n"
 620         # Set new value
 621         eval_expr expr, register
 622       else
 623         # We will use the stack to store the value
 624         @environment.add_local symbol, local_offset(n)
 625         eval_expr expr, @TEMPORARY
 626         emit "sw #{@TEMPORARY}, #{ref}\n"
 627       end
 628     end
 629
 630     # Loads the value at the given address.
 631     def load_at address, register = @TEMPORARY
 632       load_value_into_register address, register
 633       emit "lw #{register}, 0(#{register})\n"
 634       register
 635     end
 636
 637     # Loads a value into a register.
 638     # Returns the name of the register.
 639     # If the value was already in a register, the name of that
 640     # register is returned.
 641     # Else, the value is loaded into a register and the name of
 642     # that register is returned. The register to use in that case
 643     # may be specified using the optional second argument.
 644     def load_value x, register = @TEMPORARY
 645       if x == 0
 646         return "$0"
 647       elsif integer? x
 648         addiu register, "$0", x
 649         return register
 650       elsif symbol? x
 651         binding = @environment[x]
 652         if binding.kind_of? String
 653           # Value is already in a register. Return register name.
 654           return binding
 655         elsif binding.kind_of? Integer
 656           # Load value from memory.
 657           emit "lw #{register}, #{offset_reference binding}\n"
 658           return register
 659         else
 660           # Assume global
 661           emit "lui #{register}, %hi(#{x})\n"
 662           emit "addiu #{register}, %lo(#{x})\n"
 663           return register
 664         end
 665       elsif at_expr? x
 666         load_at x[1], register
 667       else
 668         raise "Don't know how to load #{x.inspect}"
 669       end
 670     end
 671
 672     # Load a value into a specific register
 673     def load_value_into_register x, register
 674       reg = load_value x, register
 675       if reg != register
 676         emit "move #{register}, #{reg}\n"
 677       end
 678     end
 679
 680     # Return the offset from the frame base at which the nth local is stored.
 681     # For register locals this is the offset at which the saved
 682     # value (from the calling function) is stored.
 683     def local_offset n
 684       -(n + 4) * @WORDSIZE
 685     end
 686
 687     # Return an $sp-relative reference for the nth (0-based) local
 688     def local_reference n
 689       offset_reference(local_offset(n))
 690     end
 691
 692     # Return the register in which the nth local (0-based) is stored, or
 693     # nil if not stored in a register
 694     def local_register n
 695       if register_local? n
 696         "$#{@REGISTER_LOCAL_BASE + n}"
 697       else
 698         nil
 699       end
 700     end
 701
 702     # Compute the maximum number of locals that would fit in the current
 703     # frame size.
 704     def max_locals
 705       # + 1, because the initial frame size has room for 1 local
 706       (@frame_size - @INITIAL_FRAME_SIZE) / @WORDSIZE + 1
 707     end
 708
 709     # Calculate the number of stack arguments,
 710     # given the total number of arguments.
 711     def number_of_stack_arguments n
 712       [0, n - @NREGISTER_ARGS].max
 713     end
 714
 715     # Given an offset relative to the base of the frame, returns
 716     # an reference to that memory location.
 717     def offset_reference offset
 718       "#{offset}($fp)"
 719     end
 720
 721     # Returns true if the nth (0-based) argument is stored in a register
 722     def register_arg? n
 723       n < @NREGISTER_ARGS
 724     end
 725
 726     # Returns true if the nth (0-based) local is stored in a register
 727     def register_local? n
 728       n < @NREGISTER_LOCALS
 729     end
 730
 731     # Return a from a function.
 732     #
 733     # _words_ may contain an expression to be evaluated. The result
 734     # of the evaluation is returned from the function.
 735     def ret *words
 736       emit "# return #{words.join ' '}\n"
 737       # Compute return value and store it in @RETURN
 738       eval_expr(words, @RETURN) unless words.empty?
 739       # Go to epilogue
 740       goto @function_end_label
 741     end
 742
 743     # Set a variable to the result of evaluating an expression
 744     def set symbol, *expr
 745       if at_expr? symbol
 746         eval_expr expr, @RETURN
 747         load_value_into_register symbol.to_s[1..-1].to_sym, @TEMPORARY
 748         emit "sw #{@RETURN}, 0(#{@TEMPORARY})\n"
 749       else
 750         x = @environment[symbol]
 751         if x == nil
 752           raise "Cannot change value of constant #{symbol}"
 753         elsif x.kind_of? String
 754           # Register
 755           eval_expr expr, x
 756         else
 757           # Should be an integer.
 758           eval_expr expr, @TEMPORARY
 759           emit "sw #{@TEMPORARY}, #{offset_reference x}\n"
 760         end
 761       end
 762     end
 763
 764     # Set the byte at _base_ + _offset_ to _value_
 765     def set_byte base, offset, value
 766       emit "# set-byte #{base} #{offset} #{value}\n"
 767       # If base is an integer, but offset isn't, swap them
 768       if !integer?(offset) && integer?(base)
 769         base, offset = [offset, base]
 770       end
 771
 772       value_reg = @TEMPORARIES.pop
 773       load_value_into_register value, value_reg
 774       begin
 775         if integer? offset
 776           base_reg = load_value base
 777           emit "sb #{value_reg}, #{offset}(#{base_reg})\n"
 778         else
 779           eval_binop [:add, base, offset], @TEMPORARY
 780           emit "sb #{value_reg}, 0(#{@TEMPORARY})\n"
 781         end
 782       ensure
 783         @TEMPORARIES.push value_reg
 784       end
 785     end
 786
 787     # Set the word at _base_ + _offset_ * +@WORDSIZE+ to _value_
 788     def set_word base, offset, value
 789       emit "# set-word #{base} #{offset} #{value}\n"
 790
 791       value_reg = @TEMPORARIES.pop
 792       load_value_into_register value, value_reg
 793       begin
 794         if integer? offset
 795           base_reg = load_value base
 796           emit "sw #{value_reg}, #{offset * @WORDSIZE}(#{base_reg})\n"
 797         else
 798           offset_reg = @TEMPORARIES.pop
 799           begin
 800             load_value_into_register offset, offset_reg
 801             base_reg = load_value base
 802             emit "sll #{offset_reg}, #{offset_reg}, 2\n"
 803             emit "add #{@TEMPORARY}, #{base_reg}, #{offset_reg}\n"
 804             emit "sw #{value_reg}, 0(#{@TEMPORARY})\n"
 805           ensure
 806             @TEMPORARIES.push offset_reg
 807           end
 808         end
 809       ensure
 810         @TEMPORARIES.push value_reg
 811       end
 812     end
 813
 814     # Define a string with the given value
 815     def string value
 816       code = ''
 817       value.each_byte do |b|
 818         if b == 92
 819           code << "\\\\"
 820         elsif b >= 32 && b < 127 && b != 34
 821           code << b.chr
 822         else
 823           code << sprintf("\\%03o", b)
 824         end
 825       end
 826       emit ".ascii \"#{code}\"\n"
 827     end
 828
 829     # Test if a value is a symbol
 830     def symbol? value
 831       value.kind_of? Symbol
 832     end
 833
 834     # Test if op is a symmetric binary operation (i.e. it will yield the
 835     # same result if the order of its source operands is changed).
 836     def symmetric_binop? op
 837       [:add, :and, :mul, :or, :xor].member? op
 838     end
 839
 840     # Call a function, re-using the current call frame if possible.
 841     def tail_call func, *args
 842       emit "# tail-call #{func} #{args.join ' '}\n"
 843
 844       # Compute number of stack arguments
 845       nstackargs = number_of_stack_arguments args.length
 846       # If we need more stack arguments than we have now,
 847       # perform a normal call and return
 848       if nstackargs > number_of_stack_arguments(@environment.args)
 849         emit "# Not enough space for proper tail call; using regular call\n"
 850         ret :call, func, *args
 851       end
 852
 853       # Back up any stack arguments we will need after we overwrite them
 854       temporaries = @TEMPORARIES.dup
 855       nlocals = @environment.locals
 856       (@NREGISTER_ARGS...args.length).each do |i|
 857         x = @environment[args[i]]
 858         if x && x[0] == :arg && x[1] >= @NREGISTER_ARGS && x[1] < i
 859           # args[i] is a stack arg, but has an index < i
 860           # That means that, by the time we get to pass arg[i] to the called
 861           # function, it will have been overwritten. So we make a backup.
 862           if temporaries.empty?
 863             # Oh dear, we're out of temporaries.
 864             # Store the value in the current stack frame, extending it
 865             # as necessary.
 866             if nlocals >= max_locals
 867               grow_stack 8
 868             end
 869             reg = load_value args[i]
 870             emit "sw #{reg}, #{local_reference nlocals}\n"
 871             args[i] = [:local, nlocals]
 872             nlocals = nlocals + 1
 873           else
 874             # Load the argument into a temporary
 875             reg = temporaries.shift
 876             load_value_into_register args[i], reg
 877             # Update args[i] so we know how to get to it later
 878             args[i] = [:reg, reg]
 879           end
 880         end
 881       end
 882
 883       # Set stack arguments
 884       (@NREGISTER_ARGS...args.length).each do |i|
 885         arg = args[i]
 886         reg = @TEMPORARY
 887
 888         # Load value
 889         if arg.kind_of? Array
 890           # Special cases, created above
 891           case arg[0]
 892           when :reg
 893             reg = arg[1]
 894           when :local
 895             emit "lw #{reg}, #{local_reference arg[1]}\n"
 896           end
 897         else
 898           load_value_into_register arg, reg
 899         end
 900
 901         # Store value in designated place
 902         emit "sw #{reg}, #{arg_reference i}\n"
 903       end
 904
 905       # Set register arguments
 906       [@NREGISTER_ARGS,args.length].min.times do |i|
 907         reg = arg_register i
 908         load_value_into_register args[i], reg
 909       end
 910
 911       # Load function address
 912       if global? func
 913         if @imports.has_key? func
 914           # Load address from global offset table
 915           emit "lw #{@FUNCTION}, %call16(#{func})(#{@GOT})\n"
 916         else
 917           # Assume label defined in this module
 918           emit "lui #{@FUNCTION}, %hi(#{func})\n"
 919           emit "addiu #{@FUNCTION}, %lo(#{func})\n"
 920         end
 921       else
 922         # Load address
 923         load_value_into_register func, "#{@FUNCTION}"
 924       end
 925
 926       # Restore saved registers
 927       [@NREGISTER_LOCALS, @environment.locals].min.times do |n|
 928         emit "lw #{local_register n}, #{local_reference n}\n"
 929       end
 930
 931       # Restore return address
 932       emit "lw $31, #{@RA_OFFSET}($fp)\n"
 933
 934       # Restore stack pointer
 935       emit "move $sp, $fp\n"
 936
 937       # Restore frame pointer
 938       emit "lw $fp, #{@FP_OFFSET}($fp)\n"
 939
 940       # Perform call
 941       emit "jr #{@FUNCTION}\n"
 942       # brach delay slot
 943       emit "nop\n"
 944     end
 945
 946     # Define a word with the given value
 947     def word value
 948       emit ".int #{value}\n"
 949     end
 950
 951     # Write generated code to the given IO object.
 952     def write io
 953       io.puts ".set noat"
 954       @sections.each do |section,code|
 955         unless code.empty?
 956           io.puts ".section #{section.to_s}"
 957           io.puts code
 958           io.puts
 959         end
 960       end
 961     end
 962
 963   end
 964
 965   # Register class for big endian MIPS
 966   Voodoo::CodeGenerator.register_generator MIPSGasGenerator,
 967                                            :architecture => :mips,
 968                                            :format => :gas
 969
 970
 971   # Register class for little endian MIPS
 972   Voodoo::CodeGenerator.register_generator MIPSGasGenerator,
 973                                            :architecture => :mipsel,
 974                                            :format => :gas
 975
 976 end