Class: Voodoo::MIPSGasGenerator

Inherits:
CommonCodeGenerator show all
Defined in:
lib/voodoo/generators/mips_gas_generator.rb

Overview

MIPS GNU Assembler Code Generator

The MIPS code generator generates assembly code for use with the GNU assembler.

Calling Convention

The first four arguments are passed in the registers $4 through $7. Any additional arguments are passed on the stack, starting at $sp + 16. Words $sp through $sp + 12 will be available for the called function to use. $sp will always be a multiple of 8.

The return address for the called function is passed in $31.

When performing a position-independent call, the address of the called function is passed in $25.

The called function will store its return value in $2.

The called function is required to preserve the values of registers $16 through $23 and register $30.

This calling convention is compatible with the System V ELF ABI.

Call Frames

Call frames have the following layout:

When a function is called, it receives a stack frame that looks like the following:

:
old frame
argn
:
arg4
empty3
empty2
empty1
empty0    <-- $sp points here

The function prologue of functions generated by this code generator creates activation frames that look as follows:

: old frame argn : arg4 arg3 arg2 arg1 arg0 return address pointer to Global Offset Table local0 : local7 local8 : localn padding <– $sp points here

In words:

The four empty slots provided by the caller are used to store arguments 0 through 3 (originally passed in $4 through $7), if necessary.

The stack frame created below the four slots provided by the caller contains the following data, in order:

  • Saved return address (originally passed in $31), if necessary.

  • Saved pointer to global offset table (computed from $25), if necessary.

  • Saved values of caller’s locals 0 through 7 (originally in $16 through $23), if necessary.

  • Values of our locals > 8, if necessary.

  • Padding to align $sp on a multiple of 8, if necessary.

In accordance with the System V ELF ABI for MIPS, the pointer to the global offset table is calculated as follows:

$gp = _gp_disp + $25

where $gp is the register to store the pointer, $25 is the register holding the address of the called function, and _gp_disp is the offset between the beginning of the function and the global offset table.

Direct Known Subclasses

MIPSELFGenerator

Instance Method Summary collapse

Methods inherited from CommonCodeGenerator

#add, #add_function, #block, #each_statement, #emit, #features, #gensym, #has_feature?, #in_section, #output_file_name, #output_file_suffix, #real_section_name, #section, #section=, #section_alias

Constructor Details

#initialize(params) ⇒ MIPSGasGenerator

Returns a new instance of MIPSGasGenerator.



98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 98

def initialize params
  @WORDSIZE = 4
  @CODE_ALIGNMENT = 0
  @DATA_ALIGNMENT = @WORDSIZE
  @FUNCTION_ALIGNMENT = @WORDSIZE

  @INITIAL_FRAME_SIZE = 2 * @WORDSIZE
  @REGISTER_ARG_BASE = 4
  @NREGISTER_ARGS = 4
  @REGISTER_LOCAL_BASE = 16
  @NREGISTER_LOCALS = 8
  @RETURN = :'$2'
  @TEMPORARY = :'$1'
  @FUNCTION = :'$25'
  @GOT = :'$28'
  @TEMPORARIES = [:'$8', :'$9', :'$10', :'$11',
                  :'$12', :'$13', :'$14', :'$15']
  @function_end_label = nil
  @imports = {}
  @if_labels = []
  super params
  @output_file_suffix = '.s'
  @features.merge! \
    :'bits-per-word' => '32',
    :'bytes-per-word' => '4'
  case @architecture
  when :mips
    @features[:'byte-order'] = 'big-endian'
  when :mipsel
    @features[:'byte-order'] = 'little-endian'
  else
    raise ArgumentError.new("#{self.class} does not support " +
                            "architecture #{@architecture}")
  end
end

Instance Method Details

#align(alignment = nil) ⇒ Object 



134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 134

def align alignment = nil
  unless alignment
    # Get default alignment
    case @section
    when :code
      alignment = @CODE_ALIGNMENT
    when :data
      alignment = @DATA_ALIGNMENT
    when :function
      alignment = @FUNCTION_ALIGNMENT
    else
      # Use data alignment as default
      alignment = @DATA_ALIGNMENT
    end
  end
  emit ".align #{alignment}\n" unless alignment == 0
end

#arg_offset(n) ⇒ Object

Return the offset from $sp at which the nth (0-based) argument is stored.



154
155
156
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 154

def arg_offset n
  @frame_size + n * @WORDSIZE
end

#arg_reference(n) ⇒ Object

Return an $sp-relative reference for the nth (0-based) argument



159
160
161
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 159

def arg_reference n
  "#{arg_offset n}($sp)"
end

#arg_register(n) ⇒ Object

Return the register in which the nth (0-based) argument is stored, or nil if not stored in a register



165
166
167
168
169
170
171
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 165

def arg_register n
  if register_arg? n
    "$#{@REGISTER_ARG_BASE + n}"
  else
    nil
  end
end

#assymetric_binop?(op) ⇒ Boolean

Test if op is a binary operation

Returns:

  • (Boolean) 


174
175
176
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 174

def assymetric_binop? op
  [:asr, :bsr, :div, :mod, :rol, :ror, :shl, :shr, :sub].member?(op)
end

#at_expr?(value) ⇒ Boolean

Test if a value is an at-expression

Returns:

  • (Boolean) 


179
180
181
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 179

def at_expr? value
  value.respond_to?(:[]) && value[0] == :'@'
end

#begin_block(*code) ⇒ Object

Begins a new block.



184
185
186
187
188
189
190
191
192
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 184

def begin_block *code
  emit "# begin block\n"
  # If we are at top-level, create a frame
  if @environment == @top_level
    create_frame count_locals(code)
  end
  environment = Environment.new @environment
  @environment = environment
end

#begin_function(formals, nlocals) ⇒ Object

Emit function prologue and declare formals as function arguments



195
196
197
198
199
200
201
202
203
204
205
206
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 195

def begin_function formals, nlocals
  if @environment != @top_level
    raise "Cannot begin function when already in a function"
  end

  emit "# function #{formals.join ' '}\n"
  environment = Environment.new @environment
  environment.add_args formals
  @environment = environment
  @function_end_label = gensym
  emit_function_prologue formals, nlocals
end

#binop?(op) ⇒ Boolean

Test if op is a binary operation

Returns:

  • (Boolean) 


209
210
211
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 209

def binop? op
  assymetric_binop?(op) || symmetric_binop?(op)
end

#byte(value) ⇒ Object

Define a byte with the given value



214
215
216
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 214

def byte value
  emit ".byte #{value}\n"
end

#call(func, *args) ⇒ Object

Call a function.



219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 219

def call func, *args
  emit "# call #{func} #{args.join ' '}\n"
  # Grow the stack frame, subject to 3 conditions:
  # 1. There must be enough space to hold all arguments
  # 2. $sp must remain a multiple of 8
  # 3. We must provide space for at least 4 words
  increment = ([args.length, 4].max * @WORDSIZE + 7) / 8 * 8
  emit "addiu $sp, $sp, -#{increment}\n"
  @frame_size = @frame_size + increment

  # Put arguments in the right places
  n = 0
  while n < args.length
    if n < @NREGISTER_ARGS
      # Put arguments up to @NREGISTER_ARGS in registers
      load_value_into_register args[n], arg_register(n)
    else
      # Put other arguments on the stack
      load_value_into_register args[n], @TEMPORARY
      emit "sw #{@TEMPORARY}, #{n * @WORDSIZE}($sp)\n"
    end
    n = n + 1
  end

  # Load function address
  if global? func
    if @imports.has_key? func
      # Load address from global offset table
      emit "lw #{@FUNCTION}, %call16(#{func})(#{@GOT})\n"
    else
      # Assume label defined in this module
      emit "lui #{@FUNCTION}, %hi(#{func})\n"
      emit "addiu #{@FUNCTION}, %lo(#{func})\n"
    end
  else
    # Load address
    load_value_into_register func, "#{@FUNCTION}"
  end

  # Perform call
  emit "jalr #{@FUNCTION}\n"
  # brach delay slot
  emit "nop\n"

  # Restore original stack frame
  emit "addiu $sp, $sp, #{increment}\n"
  @frame_size = @frame_size - increment

  # restore gp
  emit "lw #{@GOT}, #{@frame_size - 2 * @WORDSIZE}($sp)\n"
end

#common_if(comp, x, y = nil) ⇒ Object

Start a conditional using the specified branch instruction after the comparison.



273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 273

def common_if comp, x, y = nil
  emit "# #{comp} #{x} #{y}\n"

  temporaries = @TEMPORARIES.dup
  xreg = load_value x, temporaries[0]
  temporaries.delete xreg
  yreg = load_value y, temporaries[0]
  temporaries.delete yreg

  falselabel = @environment.gensym
  @if_labels.push falselabel

  case comp
  when :ifeq
    emit "bne #{xreg}, #{yreg}, #{falselabel}\n"
  when :ifge
    emit "slt #{@TEMPORARY}, #{xreg}, #{yreg}\n"
    emit "bne #{@TEMPORARY}, $0, #{falselabel}\n"
  when :ifgt
    emit "slt #{@TEMPORARY}, #{yreg}, #{xreg}\n"
    emit "beq #{@TEMPORARY}, $0, #{falselabel}\n"
  when :ifle
    emit "slt #{@TEMPORARY}, #{yreg}, #{xreg}\n"
    emit "bne #{@TEMPORARY}, $0, #{falselabel}\n"
  when :iflt
    emit "slt #{@TEMPORARY}, #{xreg}, #{yreg}\n"
    emit "beq #{@TEMPORARY}, $0, #{falselabel}\n"
  when :ifne
    emit "beq #{xreg}, #{yreg}, #{falselabel}\n"
  else
    raise "Unknown conditional: #{comp}"
  end
  emit "nop\n"
end

#count_locals(statements) ⇒ Object

Counts the number of local variables created in a sequence of statements.



310
311
312
313
314
315
316
317
318
319
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 310

def count_locals statements
   count = 0
   each_statement(statements) do |statement|
     if statement[0] == :let
       # let introduces a single local
       count = count + 1
     end
   end
   count
end

#create_frame(nlocals) ⇒ Object

Creates an activation frame which can store nlocals local variables



322
323
324
325
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 322

def create_frame nlocals
  @frame_size = (@INITIAL_FRAME_SIZE + nlocals * @WORDSIZE + 7) / 8 * 8
  emit "addiu $sp, $sp, -#{@frame_size}\n"
end

#emit_function_prologue(formals = [], nlocals = 0) ⇒ Object

Emit function prologue.



328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 328

def emit_function_prologue formals = [], nlocals = 0
  # Calculate new value for $gp
  emit "lui #{@GOT}, %hi(_gp_disp)\n"
  emit "addiu #{@GOT}, %lo(_gp_disp)\n"
  emit "addu #{@GOT}, #{@GOT}, #{@FUNCTION}\n"

  # Save parameters 0 .. 3 in the stack space that the caller
  # should have allocated for them.
  [@NREGISTER_ARGS, formals.length].min.times do |n|
    emit "sw $#{n + @REGISTER_ARG_BASE}, #{n * @WORDSIZE}($29)\n"
  end

  create_frame nlocals

  # Save return address
  emit "sw $31, #{@frame_size - @WORDSIZE}($sp)\n"

  # Save gp
  emit "sw #{@GOT}, #{@frame_size - 2 * @WORDSIZE}($sp)\n"
end

#end_block ⇒ Object

Ends the current block.



377
378
379
380
381
382
383
384
385
386
387
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 377

def end_block
  emit "# end block\n"

  # If we are returning to top level, restore stack pointer
  if @environment.parent == @top_level
    emit "addiu $sp, $sp, #{@frame_size}\n"
  end

  # Restore old value of @environment
  @environment = @environment.parent
end

#end_function ⇒ Object

End a function body



350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 350

def end_function
  if @environment == @top_level
    raise "Cannot end function when not in a function"
  end

  emit "# function epilogue\n"

  label @function_end_label
  # Restore saved locals
  [@NREGISTER_LOCALS, @environment.locals].min.times do |n|
    emit "lw #{local_register n}, #{local_reference n}\n"
  end
  # Load return address
  emit "lw $31, #{@frame_size - @WORDSIZE}($sp)\n"
  # Restore stack pointer
  emit "addiu $sp, $sp, #{@frame_size}\n"
  # Return
  emit "jr $31\n"
  emit "nop\n"

  emit "# end function\n\n"

  @function_end_label = nil
  @environment = @top_level
end

#end_if ⇒ Object

End a conditional.



390
391
392
393
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 390

def end_if
  label = @if_labels.pop
  emit "#{label}:\n"
end

#eval_binop(expr, register) ⇒ Object

Evaluate the binary operation expr and store the result in register



396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 396

def eval_binop expr, register
  temporaries = @TEMPORARIES.dup
  x = load_value expr[1], temporaries[0]
  temporaries.delete x
  y = load_value expr[2], temporaries[0]
  temporaries.delete y

  case expr[0]
  when :asr
    emit "srav #{register}, #{x}, #{y}\n"
  when :bsr
    emit "srlv #{register}, #{x}, #{y}\n"
  when :div
    emit "div $0, #{x}, #{y}\n"
    emit "mflo #{register}\n"
  when :mod
    emit "div $0, #{x}, #{y}\n"
    emit "mfhi #{register}\n"
  when :mul
    emit "mult #{x}, #{y}\n"
    emit "mflo #{register}\n"
  when :rol
    emit "subu #{@TEMPORARY}, $0, #{y}\n"
    emit "srlv #{@TEMPORARY}, #{x}, #{@TEMPORARY}\n"
    emit "sllv #{register}, #{x}, #{y}\n"
    emit "or #{register}, #{register}, #{@TEMPORARY}\n"
  when :ror
    emit "subu #{@TEMPORARY}, $0, #{y}\n"
    emit "sllv #{@TEMPORARY}, #{x}, #{@TEMPORARY}\n"
    emit "srlv #{register}, #{x}, #{y}\n"
    emit "or #{register}, #{register}, #{@TEMPORARY}\n"
  when :shl
    emit "sllv #{register}, #{x}, #{y}\n"
  when :shr
    emit "srlv #{register}, #{x}, #{y}\n"
  else
    emit "#{expr[0]} #{register}, #{x}, #{y}\n"
  end
end

#eval_expr(expr, register) ⇒ Object

Evaluate the expression expr and store the result in register



437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 437

def eval_expr expr, register
  if expr.length == 1
    # Load value
    load_value_into_register expr[0], register
  else
    # Evaluate expression
    op = expr[0]
    case op
    when :call
      call *expr[1..-1]
      emit "move #{register}, #{@RETURN}\n" if register != @RETURN
    when :'get-byte'
      get_byte expr[1], expr[2], register
    when :'get-word'
      get_word expr[1], expr[2], register
    when :not
        eval_binop [:nor, 0, expr[1]], register
    else
      if binop? op
        eval_binop expr, register
      else
        raise "Not a magic word: #{op}"
      end
    end
  end
end

#export(*symbols) ⇒ Object

Export symbols from the current section



465
466
467
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 465

def export *symbols
  symbols.each { |sym| emit ".globl #{sym}\n" }
end

#function(formals, *code) ⇒ Object

Add a function to the current section



470
471
472
473
474
475
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 470

def function formals, *code
  nlocals = count_locals code
  begin_function formals, nlocals
  code.each { |action| add section, action }
  end_function
end

#get_byte(base, offset, register) ⇒ Object

Load byte from base + offset into register



478
479
480
481
482
483
484
485
486
487
488
489
490
491
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 478

def get_byte base, offset, register
  # If base is an integer, but offset isn't, swap them
  if !integer?(offset) && integer?(base)
    base, offset = [offset, base]
  end

  if integer? offset
    base_reg = load_value base
    emit "lb #{register}, #{offset}(#{base_reg})\n"
  else
    eval_binop [:add, base, offset], @TEMPORARY
    emit "lb #{register}, 0(#{@TEMPORARY})\n"
  end
end

#get_word(base, offset, register) ⇒ Object

Load word from base + offset * _@WORDSIZE_ into register



494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 494

def get_word base, offset, register
  if integer? offset
    base_reg = load_value base
    emit "lw #{register}, #{offset * @WORDSIZE}(#{base_reg})\n"
  else
    offset_reg = @TEMPORARIES.pop
    begin
      load_value_into_register offset, offset_reg
      base_reg = load_value base
      emit "sll #{offset_reg}, #{offset_reg}, 2\n" # multiply by @WORDSIZE
      emit "add #{@TEMPORARY}, #{base_reg}, #{offset_reg}\n"
      emit "lw #{register}, 0(#{@TEMPORARY})\n"
    ensure
      @TEMPORARIES.push offset_reg
    end
  end
end

#global?(symbol) ⇒ Boolean

Test if a symbol refers to a global

Returns:

  • (Boolean) 


513
514
515
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 513

def global? symbol
  symbol?(symbol) && @environment[symbol] == nil
end

#goto(label) ⇒ Object

Jump to a label.



518
519
520
521
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 518

def goto label
  emit "j #{label}\n"
  emit "nop\n"
end

#ifelse ⇒ Object

Start the false path of a conditional.



524
525
526
527
528
529
530
531
532
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 524

def ifelse
  emit "# else\n"
  newlabel = @environment.gensym
  emit "j #{newlabel}\n"
  emit "nop\n"
  label = @if_labels.pop
  emit "#{label}:\n"
  @if_labels.push newlabel
end

#ifeq(x, y) ⇒ Object

Test if x is equal to y



535
536
537
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 535

def ifeq x, y
  common_if :ifeq, x, y
end

#ifge(x, y) ⇒ Object

Test if x is greater than or equal to y



540
541
542
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 540

def ifge x, y
  common_if :ifge, x, y
end

#ifgt(x, y) ⇒ Object

Test if x is strictly greater than y



545
546
547
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 545

def ifgt x, y
  common_if :ifgt, x, y
end

#ifle(x, y) ⇒ Object

Test if x is less than or equal to y



550
551
552
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 550

def ifle x, y
  common_if :ifle, x, y
end

#iflt(x, y) ⇒ Object

Test if x is strictly less than y



555
556
557
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 555

def iflt x, y
  common_if :iflt, x, y
end

#ifne(x, y) ⇒ Object

Test if x different from y



560
561
562
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 560

def ifne x, y
  common_if :ifne, x, y
end

#import(*symbols) ⇒ Object

Import labels into the current section



565
566
567
568
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 565

def import *symbols
  # Record imported labels in @imports
  symbols.each { |sym| @imports[sym] = sym }
end

#integer?(value) ⇒ Boolean

Test if a value is an integer

Returns:

  • (Boolean) 


571
572
573
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 571

def integer? value
  value.kind_of? Integer
end

#label(name) ⇒ Object

Emit a label



576
577
578
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 576

def label name
  emit "#{name}:\n"
end

#let(symbol, *expr) ⇒ Object

Introduce a new local variable



581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 581

def let symbol, *expr
  emit "# let #{symbol} #{expr.join ' '}\n"
  n = @environment.locals
  @environment.add_local symbol

  # Extend stack frame, if necessary.
  # This should never be necessary, because we allocate enough
  # space in the top-level function or block.
  if @environment.locals > max_locals
    $stderr.puts "WARNING: Stack frame too small. Possible BUG"
    $stderr.puts "Frame size #{@frame_size}, max locals #{max_locals}" +
                 ", actual locals #{@environment.locals}"
    # Extend frame by 8 bytes, to keep $sp a multiple of 8
    emit "addiu $sp, $sp, -8\n"
    @frame_size = @frame_size + 8
  end

  register = local_register n
  ref = local_reference n
  if register
    # We will use a register to store the value
    # Save current value of register
    emit "sw #{register}, #{ref}\n"
    # Set new value
    eval_expr expr, register
  else
    # We will use the stack to store the value
    eval_expr expr, @TEMPORARY
    emit "sw #{@TEMPORARY}, #{ref}\n"
  end
end

#load_at(address, register = @TEMPORARY) ⇒ Object

Load the value at the given address.



614
615
616
617
618
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 614

def load_at address, register = @TEMPORARY
  load_value_into_register address, register
  emit "lw #{register}, 0(#{register})\n"
  register
end

#load_value(x, register = @TEMPORARY) ⇒ Object

Load a value into a register. Returns the name of the register. If the value was already in a register, the name of that register is returned. Else, the value is loaded into a register and the name of that register is returned. The register to use in that case may be specified using the optional second argument.



627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 627

def load_value x, register = @TEMPORARY
  if x == 0
    return "$0"
  elsif integer? x
    if x >= -32768 && x <= 32767
      emit "addiu #{register}, $0, #{x}\n"
      return register
    else
      emit "lui #{register}, #{x >> 16}\n"
      emit "ori #{register}, #{register}, #{x & 0xffff}\n"
      return register
    end
  elsif symbol? x
    binding = @environment[x]
    if binding
      case binding[0]
      when :arg
        emit "lw #{register}, #{arg_reference binding[1]}\n"
        return register
      when :local
        n = binding[1]
        if register_local? n
          return local_register(n)
        else
          emit "lw #{register}, #{local_reference n}\n"
          return register
        end
      else
        raise "Don't know how to load #{x.inspect}"
      end
    else
      # Assume global
      emit "lui #{register}, %hi(#{x})\n"
      emit "addiu #{register}, %lo(#{x})\n"
      return register
    end
  elsif at_expr? x
    load_at x[1], register
  else
    raise "Don't know how to load #{x.inspect}"
  end
end

#load_value_into_register(x, register) ⇒ Object

Load a value into a specific register



671
672
673
674
675
676
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 671

def load_value_into_register x, register
  reg = load_value x, register
  if reg != register
    emit "move #{register}, #{reg}\n"
  end
end

#local_offset(n) ⇒ Object

Return the offset from $sp at which the nth (0-based) local variable is stored. For register locals this is the offset at which the saved value (from the calling function) is stored.



681
682
683
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 681

def local_offset n
  @frame_size - @INITIAL_FRAME_SIZE - (n + 1) * @WORDSIZE
end

#local_reference(n) ⇒ Object

Return an $sp-relative reference for the nth (0-based) local



686
687
688
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 686

def local_reference n
  "#{local_offset n}($sp)"
end

#local_register(n) ⇒ Object

Return the register in which the nth local (0-based) is stored, or nil if not stored in a register



692
693
694
695
696
697
698
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 692

def local_register n
  if register_local? n
    "$#{@REGISTER_LOCAL_BASE + n}"
  else
    nil
  end
end

#max_locals ⇒ Object

Compute the maximum number of locals that would fit in the current frame size.



702
703
704
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 702

def max_locals
  (@frame_size - @INITIAL_FRAME_SIZE) / @WORDSIZE
end

#number_of_stack_arguments(n) ⇒ Object

Calculate the number of stack arguments, given the total number of arguments.



708
709
710
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 708

def number_of_stack_arguments n
  [0, n - @NREGISTER_ARGS].max
end

#register_arg?(n) ⇒ Boolean

Returns true if the nth (0-based) argument is stored in a register

Returns:

  • (Boolean) 


713
714
715
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 713

def register_arg? n
  n < @NREGISTER_ARGS
end

#register_local?(n) ⇒ Boolean

Returns true if the nth (0-based) local is stored in a register

Returns:

  • (Boolean) 


718
719
720
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 718

def register_local? n
  n < @NREGISTER_LOCALS
end

#ret(*words) ⇒ Object

Return a from a function.

words may contain an expression to be evaluated. The result of the evaluation is returned from the function.



726
727
728
729
730
731
732
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 726

def ret *words
  emit "# return #{words.join ' '}\n"
  # Compute return value and store it in @RETURN
  eval_expr(words, @RETURN) unless words.empty?
  # Go to epilogue
  goto @function_end_label
end

#set(symbol, *expr) ⇒ Object

Set a variable to the result of evaluating an expression



735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 735

def set symbol, *expr
  emit "# set #{symbol} #{expr.join ' '}\n"

  x = @environment[symbol]
  if x == nil
    raise "Cannot change value of constant #{symbol}"
  end

  if x[0] == :local
    register = local_register x[1]
  else
    register = nil
  end

  if register
    # Set new value
    eval_expr expr, register
  else
    case x[0]
    when :local
      ref = local_reference x[1]
    when :arg
      ref = arg_reference x[1]
    else
      raise "??? #{sym} is neither a local nor an argument"
    end
    eval_expr expr, @TEMPORARY
    emit "sw #{@TEMPORARY}, #{ref}\n"
  end
end

#set_byte(base, offset, value) ⇒ Object

Set the byte at base + offset to value



767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 767

def set_byte base, offset, value
  emit "# set-byte #{base} #{offset} #{value}\n"
  # If base is an integer, but offset isn't, swap them
  if !integer?(offset) && integer?(base)
    base, offset = [offset, base]
  end

  value_reg = @TEMPORARIES.pop
  load_value_into_register value, value_reg
  begin
    if integer? offset
      base_reg = load_value base
      emit "sb #{value_reg}, #{offset}(#{base_reg})\n"
    else
      eval_binop [:add, base, offset], @TEMPORARY
      emit "sb #{value_reg}, 0(#{@TEMPORARY})\n"
    end
  ensure
    @TEMPORARIES.push value_reg
  end
end

#set_word(base, offset, value) ⇒ Object

Set the word at base + offset * @WORDSIZE to value



790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 790

def set_word base, offset, value
  emit "# set-word #{base} #{offset} #{value}\n"

  value_reg = @TEMPORARIES.pop
  load_value_into_register value, value_reg
  begin
    if integer? offset
      base_reg = load_value base
      emit "sw #{value_reg}, #{offset * @WORDSIZE}(#{base_reg})\n"
    else
      offset_reg = @TEMPORARIES.pop
      begin
        load_value_into_register offset, offset_reg
        base_reg = load_value base
        emit "sll #{offset_reg}, #{offset_reg}, 2\n"
        emit "add #{@TEMPORARY}, #{base_reg}, #{offset_reg}\n"
        emit "sw #{value_reg}, 0(#{@TEMPORARY})\n"
      ensure
        @TEMPORARIES.push offset_reg
      end
    end
  ensure
    @TEMPORARIES.push value_reg
  end
end

#string(value) ⇒ Object

Define a string with the given value



817
818
819
820
821
822
823
824
825
826
827
828
829
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 817

def string value
  code = ''
  value.each_byte do |b|
    if b == 92
      code << "\\\\"
    elsif b >= 32 && b < 127 && b != 34
      code << b.chr
    else
      code << sprintf("\\%03o", b)
    end
  end
  emit ".ascii \"#{code}\"\n"
end

#symbol?(value) ⇒ Boolean

Test if a value is a symbol

Returns:

  • (Boolean) 


832
833
834
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 832

def symbol? value
  value.kind_of? Symbol
end

#symmetric_binop?(op) ⇒ Boolean

Test if op is a symmetric binary operation (i.e. it will yield the same result if the order of its source operands is changed).

Returns:

  • (Boolean) 


838
839
840
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 838

def symmetric_binop? op
  [:add, :and, :mul, :or, :xor].member? op
end

#tail_call(func, *args) ⇒ Object

Call a function, re-using the current call frame if possible.



843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 843

def tail_call func, *args
  emit "# tail-call #{func} #{args.join ' '}\n"

  # Compute number of stack arguments
  nstackargs = number_of_stack_arguments args.length
  # If we need more stack arguments than we have now,
  # perform a normal call and return
  if nstackargs > number_of_stack_arguments(@environment.args)
    emit "# Not enough space for proper tail call; using regular call\n"
    ret :call, func, *args
  end

  # Back up any stack arguments we will need after we overwrite them
  temporaries = @TEMPORARIES.dup
  nlocals = @environment.locals
  (@NREGISTER_ARGS...args.length).each do |i|
    x = @environment[args[i]]
    if x && x[0] == :arg && x[1] >= @NREGISTER_ARGS && x[1] < i
      # args[i] is a stack arg, but has an index < i
      # That means that, by the time we get to pass arg[i] to the called
      # function, it will have been overwritten. So we make a backup.
      if temporaries.empty?
        # Oh dear, we're out of temporaries.
        # Store the value in the current stack frame, extending it
        # as necessary.
        if nlocals >= max_locals
          emit "addiu $sp, -8\n"
          @frame_size = @frame_size + 8
        end
        reg = load_value args[i]
        emit "sw #{reg}, #{local_reference nlocals}\n"
        args[i] = [:local, nlocals]
        nlocals = nlocals + 1
      else
        # Load the argument into a temporary
        reg = temporaries.shift
        load_value_into_register args[i], reg
        # Update args[i] so we know how to get to it later
        args[i] = [:reg, reg]
      end
    end
  end

  # Set stack arguments
  (@NREGISTER_ARGS...args.length).each do |i|
    arg = args[i]
    reg = @TEMPORARY

    # Load value
    if arg.kind_of? Array
      # Special cases, created above
      case arg[0]
      when :reg
        reg = arg[1]
      when :local
        emit "lw #{reg}, #{local_reference arg[1]}\n"
      end
    else
      load_value_into_register arg, reg
    end

    # Store value in designated place
    emit "sw #{reg}, #{arg_reference i}\n"
  end

  # Set register arguments
  [@NREGISTER_ARGS,args.length].min.times do |i|
    reg = arg_register i
    load_value_into_register args[i], reg
  end

  # Restore saved registers
  [@NREGISTER_LOCALS, @environment.locals].min.times do |n|
    emit "lw #{local_register n}, #{local_reference n}\n"
  end
  # Restore return address
  emit "lw $31, #{@frame_size - @WORDSIZE}($sp)\n"

  # Adjust stack pointer
  emit "addiu $sp, #{@frame_size}\n"

  # Load function address
  if global? func
    if @imports.has_key? func
      # Load address from global offset table
      emit "lw #{@FUNCTION}, %call16(#{func})(#{@GOT})\n"
    else
      # Assume label defined in this module
      emit "lui #{@FUNCTION}, %hi(#{func})\n"
      emit "addiu #{@FUNCTION}, %lo(#{func})\n"
    end
  else
    # Load address
    load_value_into_register func, "#{@FUNCTION}"
  end

  # Perform call
  emit "jr #{@FUNCTION}\n"
  # brach delay slot
  emit "nop\n"
end

#word(value) ⇒ Object

Define a word with the given value



946
947
948
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 946

def word value
  emit ".int #{value}\n"
end

#write(io) ⇒ Object

Write generated code to the given IO object.



951
952
953
954
955
956
957
958
959
960
 
# File 'lib/voodoo/generators/mips_gas_generator.rb', line 951

def write io
  io.puts ".set noat"
  @sections.each do |section,code|
    unless code.empty?
      io.puts ".section #{section.to_s}"
      io.puts code
      io.puts
    end
  end
end