Class: Voodoo::CommonCodeGenerator

Inherits:
Object
  • Object
show all
Defined in:
lib/voodoo/generators/common_code_generator.rb

Overview

Common base class for code generators.

Code generators are expected to implement the following methods:

  • #new

  • #add

  • #add_function

  • #features

  • #gensym

  • #has_feature?

  • #output_file_name

  • #output_file_suffix

  • #saved_frame_size

This class contains base implementations of some of these methods, which can be used and/or overridden by subclasses.

An example of how to use the code generators provided by this module is provided on the main page of the documentation of the Voodoo module.

Direct Known Subclasses

ARMGasGenerator, MIPSGasGenerator, NasmGenerator

Defined Under Namespace

Classes: Environment

Instance Method Summary collapse

Constructor Details

#initialize(params = {}) ⇒ CommonCodeGenerator

Initializes the code generator. params is a hash of key-value pairs, and can be used to pass additional parameters to the generator. Standard parameters are :architecture and :format, which indicate the architecture and the output format. If these are not supplied, default values will be used. Subclasses may define additional parameters.



36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 36

def initialize params = {}
  @architecture = params[:architecture] || Config.default_architecture
  @format = params[:format] || Config.default_format
  @sections = {}
  @section_aliases = {}
  # Default section aliases. Subclasses can start from scratch by
  # doing @section_aliases = {}
  section_alias :code, ".text"
  section_alias :functions, :code
  section_alias :data, ".data"
  self.section = :code
  @top_level = Environment.initial_environment
  @environment = @top_level
  @output_file_suffix = '.o'
  @open_labels = []     # Labels for which we must emit size annotations
  @relocated_symbols = Set.new
  @symbol_tracker = SymbolTracker.new
  @features = {
    :voodoo => "1.1"    # Voodoo language version
  }
end

Instance Method Details

#add(section, *code) ⇒ Object

Adds code to the given section.

Examples:

add :code, [:return, 0]
add :data, [:align], [:label, :xyzzy], [:word, 42]

This method implements the required functionality in terms of a number of methods for individual incantations. These must be implemented by subclasses, although default implementations may be provided by CommonCodeGenerator. The following list contains the methods that the add method relies on. Methods that are provided by this class have been marked with a star. In general, these methods will require some functionality to be implemented by subclasses.

  • #align (*)

  • #block (*)

  • #byte

  • #call

  • #comment

  • #emit_label_size

  • #end_if

  • #export (*)

  • #function (*)

  • #goto

  • #group

  • #ifeq

  • #ifge

  • #ifgt

  • #ifle

  • #iflt

  • #ifne

  • #import (*)

  • #label (*)

  • #let

  • #restore_frame (*)

  • #restore_locals (*)

  • #ret

  • #save_frame (*)

  • #save_locals (*)

  • #set

  • #set_byte

  • #set_word

  • #string

  • #word



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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 103

def add section, *code
  in_section section do
    code.each do |action|
      keyword, args = action[0], action[1..-1]
      case keyword
      when :block
        emit_voodoo :block
        block *args
        emit_voodoo :end, :block
      when :function
        emit_voodoo :function, *args[0]
        function args[0], *args[1..-1]
        emit_voodoo :end, :function
      when :group
        emit_voodoo :group
        old_open_labels = @open_labels
        begin
          @open_labels = []
          args.each { |statement| add section, statement }
        ensure
          @open_labels = old_open_labels
        end
        emit_voodoo :end, :group
      when :ifeq, :ifge, :ifgt, :ifle, :iflt, :ifne
        emit_voodoo keyword, *args[0]
        truebody = action[2]
        falsebody = action[3]
        send keyword, action[1][0], action[1][1]
        add section, *truebody
        if falsebody && !falsebody.empty?
          emit_voodoo :else
          ifelse
          add section, *falsebody
        end
        emit_voodoo :end, :if
        end_if
      when :label, :string, :word
        send *action
      when :return
        emit_voodoo *action
        send :ret, *args
      else
        emit_voodoo *action
 underscored = keyword.to_s.gsub('-', '_').to_sym
        send underscored, *args
      end

      # If we are on top-level and we have open labels and we just
      # emitted something that isn't a label, emit size annotations
      # for all open labels.
      if !@open_labels.empty? && keyword != :label &&
          @environment == @top_level
        @open_labels.each { |name| emit_label_size name }
        @open_labels.clear
      end
    end
  end
end

#add_function(formals, *code) ⇒ Object

Adds a function.

Parameters:

formals

an Array of formal parameter names

code

an Array of actions to be used as the function’s body

Example:

add_function [:n], [:return, :add, :n, 1]



170
171
172
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 170

def add_function formals, *code
  add :functions, [:function, formals] + code
end

#align(alignment = nil) ⇒ Object

Emits a directive to align the code or data following this statement. If alignment is given, aligns on the next multiple of alignment bytes. Else, uses the default alignment for the current section.

This method requires the presence of a default_alignment method to calculate the default alignment for a given section, and an emit_align method to actually emit the target-specific code to align to a multiple of a given number of bytes. An implementation of default_alignment is provided in this class.



218
219
220
221
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 218

def align alignment = nil
  alignment = default_alignment if alignment == nil
  emit_align alignment unless alignment == 0
end

#assymetric_binop?(op) ⇒ Boolean

Tests if op is a binary operation.

Returns:

  • (Boolean) 


224
225
226
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 224

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

#at_expr?(value) ⇒ Boolean

Tests if a value is an at-expression.

Returns:

  • (Boolean) 


229
230
231
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 229

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

#binop?(op) ⇒ Boolean

Tests if op is a binary operation.

Returns:

  • (Boolean) 


234
235
236
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 234

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

#block(*code) ⇒ Object

Processes code in its own block. Local variables can be introduced inside the block. They will be deleted at the end of the block.

This method requires subclasses to implement begin_block and end_block.



244
245
246
247
248
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 244

def block *code
  begin_block *code
  code.each { |action| add section, action }
  end_block
end

#count_locals(statements) ⇒ Object

Returns the number of local variable slots required by a sequence of statements.



252
253
254
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 252

def count_locals statements
  count_locals_helper statements, 0, 0
end

#default_alignment(section = @section) ⇒ Object

Returns the default alignment for the given section. If no section is specified, returns the alignment for the current section.



259
260
261
262
263
264
265
266
267
268
269
270
271
272
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 259

def default_alignment section = @section
  # Get default alignment
  case section
  when :code
    @CODE_ALIGNMENT
  when :data
    @DATA_ALIGNMENT
  when :function
    @FUNCTION_ALIGNMENT
  else
    # Use data alignment as default
    @DATA_ALIGNMENT
  end
end

#each_statement(statements, &block) ⇒ Object

Invokes block with each statement in the given list of statements. This iterator also descends into nested statements, calling block first with the outer statement, and then for each inner statement.



278
279
280
281
282
283
284
285
286
287
288
289
290
291
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 278

def each_statement statements, &block
  statements.each do |statement|
    yield statement
    case statement[0]
    when :block
      each_statement statement[1..-1], &block
    when :function
      each_statement statement[2..-1], &block
    when :ifeq, :ifle, :iflt, :ifge, :ifgt, :ifne
      each_statement statement[2], &block
      each_statement(statement[3], &block) if statement.length > 3
    end
  end
end

#emit(code) ⇒ Object

Adds code to the current section.



294
295
296
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 294

def emit code
  @sections[real_section_name(@section)] << code
end

#emit_import(*symbols) ⇒ Object

Emits code for an import incantation. For some targets, no code actually need be emitted, so the default implementation of this method does nothing.



301
302
303
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 301

def emit_import *symbols
  # No need to emit anything.
end

#emit_label(name) ⇒ Object

Emits a label.



306
307
308
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 306

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

#emit_voodoo(*code) ⇒ Object

Emits a comment with the given Voodoo code.



311
312
313
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 311

def emit_voodoo *code
  comment code.join(' ')
end

#export(*symbols) ⇒ Object

Declares that the given symbols are to be externally visible. Requires subclasses to implement emit_export.



317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 317

def export *symbols
  used_earlier = symbols_used_unrelocated symbols
  # Exporting symbols after they have been used is not allowed.
  error = nil
  unless used_earlier.empty?
    error = CodeGenerator::SymbolsExportedAfterUseError.new(used_earlier)
  end
  begin
    if real_section_name(section) == ".data"
      @relocated_symbols.merge symbols
    end
    @symbol_tracker.use *symbols
    emit_export *symbols
  ensure
    raise error unless error == nil
  end
end

#features ⇒ Object

Returns a hash describing the features supported by this code generator. The keys in this hash are the names of the supported features. The associated values are strings providing additional information about the feature, such as a version number.



178
179
180
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 178

def features
  @features
end

#function(formals, *code) ⇒ Object

Adds a function to the current section. Requires subclasses to implement begin_function and end_function.



337
338
339
340
341
342
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 337

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

#gensym ⇒ Object

Returns a new, unused symbol.



183
184
185
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 183

def gensym
  Environment.gensym
end

#global?(symbol) ⇒ Boolean

Tests if a symbol refers to a global.

Returns:

  • (Boolean) 


345
346
347
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 345

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

#has_feature?(name) ⇒ Boolean

Returns true if a feature is supported by this generator, false otherwise.

Returns:

  • (Boolean) 


189
190
191
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 189

def has_feature? name
  @features.has_key? name
end

#import(*symbols) ⇒ Object

Declares that the given symbols are imported from an external object. This function calls emit_import to actually emit code for the import statements. The default implementation of emit_import does nothing, so targets where code is required for imports will want to override emit_import.



354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 354

def import *symbols
  used_earlier = symbols_used_unrelocated symbols
  # Importing symbols after they have been used is not allowed.
  error = nil
  unless used_earlier.empty?
    error = CodeGenerator::SymbolsImportedAfterUseError.new(used_earlier)
  end
  begin
    @relocated_symbols.merge symbols
    @symbol_tracker.define *symbols
    emit_import *symbols
  ensure
    raise error unless error == nil
  end
end

#in_section(name, &block) ⇒ Object

Executes a block of code using the given section as the current section.



371
372
373
374
375
376
377
378
379
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 371

def in_section name, &block
  oldsection = @section
  self.section = name
  begin
    yield
  ensure
    self.section = oldsection
  end
end

#integer?(value) ⇒ Boolean

Tests if a value is an integer.

Returns:

  • (Boolean) 


382
383
384
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 382

def integer? value
  value.kind_of? Integer
end

#label(name) ⇒ Object

Creates a label. Besides emitting the label name, this also annotates top-level objects with type and size as required for ELF shared libraries. Requires subclasses to emit emit_label and emit_label_type.



390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 390

def label name
  # If we are at top level, emit type directive and arrange to
  # emit size directive.
  if @environment == @top_level
    case real_section_name(section)
    when ".text"
      type = :code
    else
      type = :data
    end
    emit_label_type name, type
    @open_labels << name
  end
  @symbol_tracker.define name
  emit_label name
end

#local_register(n) ⇒ Object

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



409
410
411
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 409

def local_register n
  @LOCAL_REGISTERS[n + number_of_register_arguments]
end

#number_of_register_arguments(n = @environment.args) ⇒ Object

Calculates the number of register arguments, given the total number of arguments.



415
416
417
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 415

def number_of_register_arguments n = @environment.args
  [n, @NREGISTER_ARGS].min
end

#number_of_stack_arguments(n = @environment.args) ⇒ Object

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



421
422
423
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 421

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

#output_file_name(input_name) ⇒ Object

Given an input file name, returns the canonical output file name for this code generator.



195
196
197
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 195

def output_file_name input_name
  input_name.sub(/\.voo$/, '') + @output_file_suffix
end

#output_file_suffix ⇒ Object

Returns the canonical output file suffix for this code generator.



200
201
202
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 200

def output_file_suffix
  @output_file_suffix
end

#real_section_name(name) ⇒ Object

Gets the real name of a section. Given a section name which may be an alias, this method returns the real name of the section.



428
429
430
431
432
433
434
435
436
437
438
439
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 428

def real_section_name name
  given_name = name
  while true
    x = @section_aliases[name]
    break if x == nil       # Not an alias, exit loop and return name
    name = x
    # If name == given_name, we're back where we started. Continuing
    # would have us loop forever. Just return what we have now.
    break if name == given_name
  end
  name
end

#register?(x) ⇒ Boolean

Returns true if operand is a register, false otherwise.

Returns:

  • (Boolean) 


442
443
444
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 442

def register? x
  x.kind_of? Symbol
end

#register_arg?(n) ⇒ Boolean

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

Returns:

  • (Boolean) 


447
448
449
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 447

def register_arg? n
  n < @NREGISTER_ARGS
end

#registers_for_locals(locals = []) ⇒ Object

Given some local variable names, returns the registers those variables are stored in. If no variable names are given, returns all registers used to store local variables.

Requires @LOCAL_REGISTERS_SET, a set of registers that are used to store local variables.



457
458
459
460
461
462
463
464
465
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 457

def registers_for_locals locals = []
  locals = @environment.symbols.keys if locals.empty?
  registers = []
  locals.each do |sym|
    reg = @environment[sym]
    registers << reg if @LOCAL_REGISTERS_SET.include? @environment[sym]
  end
  registers
end

#restore_frame(frame) ⇒ Object

Restores the frame saved at the given location. Requires @SAVE_FRAME_REGISTERS, an array of register names that must be restored.



470
471
472
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 470

def restore_frame frame
  restore_registers_from_frame frame, @SAVE_FRAME_REGISTERS
end

#restore_locals(frame, *locals) ⇒ Object

Restores local variables from a saved frame.



475
476
477
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 475

def restore_locals frame, *locals
  restore_registers_from_frame frame, registers_for_locals(locals)
end

#restore_registers_from_frame(frame, registers) ⇒ Object

Helper function for restore_frame and restore_locals.

Requires @SAVED_FRAME_LAYOUT, a map from register names to positions in a saved frame, emit_load_word to load registers from memory, and load_value_into_register to load a Voodoo value into a CPU register.



484
485
486
487
488
489
490
491
492
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 484

def restore_registers_from_frame frame, registers
  with_temporary do |temporary|
    load_value_into_register frame, temporary
    registers.each do |register|
      i = @SAVED_FRAME_LAYOUT[register]
      emit_load_word register, temporary, i
    end
  end
end

#save_frame(frame) ⇒ Object

Saves the current frame to the given location.

Requires @SAVE_FRAME_REGISTERS, an array of names of registers that must be saved, and @LOCAL_REGISTERS, the list of registers that are used to store values of local variables.



499
500
501
502
503
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 499

def save_frame frame
  registers_to_save = @SAVE_FRAME_REGISTERS -
    (@saved_registers & @LOCAL_REGISTERS)
  save_registers_to_frame frame, registers_to_save
end

#save_frame_and_locals(frame, *locals) ⇒ Object

Saves the current frame to the given location. If locals are given, saves those locals to the frame, too. If no locals are given, saves all locals.

Requires @SAVE_FRAME_REGISTERS, an array of names of registers that must be saved, and @LOCAL_REGISTERS, the list of registers that are used to store values of local variables.



513
514
515
516
517
518
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 513

def save_frame_and_locals frame, *locals
  registers_to_save = (@SAVE_FRAME_REGISTERS -
    (@saved_registers & @LOCAL_REGISTERS)) |
    registers_for_locals(locals)
  save_registers_to_frame frame, registers_to_save
end

#save_locals(frame, *locals) ⇒ Object

Saves local variables to the given frame. If no locals are specified, saves all locals. If locals are specified, saves only the specified ones.



523
524
525
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 523

def save_locals frame, *locals
  save_registers_to_frame frame, registers_for_locals(locals)
end

#save_registers_to_frame(frame, registers) ⇒ Object

Helper function for save_frame and save_locals.

Requires @SAVED_FRAME_LAYOUT, a map from register names to positions in a saved frame, emit_store_word to store registers in memory, and load_value_into_register to load a Voodoo value into a CPU register.



532
533
534
535
536
537
538
539
540
541
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 532

def save_registers_to_frame frame, registers
  return if registers.empty?
  with_temporary do |temporary|
    load_value_into_register frame, temporary
    registers.each do |register|
      i = @SAVED_FRAME_LAYOUT[register]
      emit_store_word register, temporary, i
    end
  end
end

#saved_frame_size ⇒ Object

Returns the number of bytes necessary to save the current frame.



544
545
546
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 544

def saved_frame_size
  @SAVED_FRAME_LAYOUT.length * @WORDSIZE
end

#section(name = nil) ⇒ Object

Returns the name of the current section. If a name is given, sets the name of the current section first.



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

def section name = nil
  self.section = name if name
  @section
end

#section=(name) ⇒ Object

Sets the current section.



549
550
551
552
553
554
555
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 549

def section= name
  real_name = real_section_name name
  @section = name
  unless @sections.has_key? real_name
    @sections[real_name] = ''
  end
end

#section_alias(alias_name, original_name) ⇒ Object

Sets up alias_name to refer to the same section as original_name.



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

def section_alias alias_name, original_name
  @section_aliases[alias_name] = original_name
end

#stack_align(n) ⇒ Object

Given n, returns the nearest multiple of @STACK_ALIGNMENT that is >= n.



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

def stack_align n
  (n + @STACK_ALIGNMENT - 1) / @STACK_ALIGNMENT * @STACK_ALIGNMENT
end

#substitute_number(key) ⇒ Object

Substitutes a numeric value for a given substitution key.



581
582
583
584
585
586
587
588
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 581

def substitute_number key
  case key
  when :'saved-frame-size'
	saved_frame_size
  else
	@features[key].to_i
  end
end

#substitution?(x) ⇒ Boolean

Tests if a value is a substitution.

Returns:

  • (Boolean) 


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

def substitution? x
  x.respond_to?(:[]) && x[0] == :'%'
end

#symbol?(value) ⇒ Boolean

Tests if a value is a symbol.

Returns:

  • (Boolean) 


591
592
593
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 591

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) 


597
598
599
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 597

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

#undefined_symbols ⇒ Object

Returns a set of symbols that have been used, but not defined.



602
603
604
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 602

def undefined_symbols
  @symbol_tracker.used_but_undefined_symbols
end

#with_temporaries(n, &block) ⇒ Object

Executes a block of code, passing the block the name of n unused temporary registers.

Requires @TEMPORARIES, an array of temporary registers.



610
611
612
613
614
615
616
617
618
619
620
621
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 610

def with_temporaries n, &block
  if @TEMPORARIES.length < n
    raise "Out of temporary registers"
  else
    temporaries = @TEMPORARIES.shift n
    begin
      yield *temporaries
    ensure
      @TEMPORARIES.unshift *temporaries
    end
  end
end

#with_temporary(&block) ⇒ Object

Executes a block of code, passing the block the name of an unused temporary register as its first argument.



625
626
627
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 625

def with_temporary &block
  with_temporaries 1, &block
end

#write(io) ⇒ Object

Writes generated code to the given IO object.



630
631
632
633
634
635
636
637
638
 
# File 'lib/voodoo/generators/common_code_generator.rb', line 630

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