reject programs that export symbols after they have been used

[voodoo-lang.git] / lib / voodoo / generators / common_code_generator.rb

require 'set'
require 'voodoo/symbol_tracker'

module Voodoo
  # 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.
  #
  class CommonCodeGenerator
    # == Public Interface
    #
    # These methods implement the public interface of code generators.

    # 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.
    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

    # 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
    #
    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

    # 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]
    def add_function formals, *code
      add :functions, [:function, formals] + code
    end

    # 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.
    def features
      @features
    end

    # Returns a new, unused symbol.
    def gensym
      Environment.gensym
    end

    # Returns true if a feature is supported by this generator,
    # false otherwise.
    def has_feature? name
      @features.has_key? name
    end

    # Given an input file name, returns the canonical output file name
    # for this code generator.
    def output_file_name input_name
      input_name.sub(/\.voo$/, '') + @output_file_suffix
    end

    # Returns the canonical output file suffix for this code generator.
    def output_file_suffix
      @output_file_suffix
    end

    # == Helper Methods
    #
    # These methods are intended to be used by subclasses.

    # 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.
    def align alignment = nil
      alignment = default_alignment if alignment == nil
      emit_align alignment unless alignment == 0
    end

    # Tests if op is a binary operation.
    def assymetric_binop? op
      [:asr, :bsr, :div, :mod, :rol, :ror, :shl, :shr, :sub].member?(op)
    end

    # Tests if a value is an at-expression.
    def at_expr? value
      value.respond_to?(:[]) && value[0] == :'@'
    end

    # Tests if op is a binary operation.
    def binop? op
      assymetric_binop?(op) || symmetric_binop?(op)
    end

    # 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.
    def block *code
      begin_block *code
      code.each { |action| add section, action }
      end_block
    end

    # Returns the number of local variable slots required by
    # a sequence of statements.
    def count_locals statements
      count_locals_helper statements, 0, 0
    end

    # Returns the default alignment for the given section.
    # If no section is specified, returns the alignment for the current
    # section.
    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

    # 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.
    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

    # Adds code to the current section.
    def emit code
      @sections[real_section_name(@section)] << code
    end

    # Emits code for an import incantation. For some targets, no code actually
    # need be emitted, so the default implementation of this method does
    # nothing.
    def emit_import *symbols
      # No need to emit anything.
    end
 
    # Emits a label.
    def emit_label name
      emit "#{name}:\n"
    end

    # Emits a comment with the given Voodoo code.
    def emit_voodoo *code
      comment code.join(' ')
    end

    # Declares that the given symbols are to be externally visible.
    # Requires subclasses to implement emit_export.
    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

    # Adds a function to the current section.
    # Requires subclasses to implement begin_function and end_function.
    def function formals, *code
      nlocals = count_locals code
      begin_function formals, nlocals
      code.each { |action| add section, action }
      end_function
    end

    # Tests if a symbol refers to a global.
    def global? symbol
      symbol?(symbol) && @environment[symbol] == nil
    end

    # 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.
    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

    # Executes a block of code using the given section as the current section.
    def in_section name, &block
      oldsection = @section
      self.section = name
      begin
        yield
      ensure
        self.section = oldsection
      end
    end

    # Tests if a value is an integer.
    def integer? value
      value.kind_of? Integer
    end

    # 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.
    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

    # Returns the register in which the nth local (0-based) is stored, or
    # nil if not stored in a register.
    def local_register n
      @LOCAL_REGISTERS[n + number_of_register_arguments]
    end

    # Calculates the number of register arguments,
    # given the total number of arguments.
    def number_of_register_arguments n = @environment.args
      [n, @NREGISTER_ARGS].min
    end

    # Calculate the number of stack arguments,
    # given the total number of arguments.
    def number_of_stack_arguments n = @environment.args
      [0, n - @NREGISTER_ARGS].max
    end

    # 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.
    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

    # Returns true if operand is a register, false otherwise.
    def register? x
      x.kind_of? Symbol
    end

    # Returns true if the nth (0-based) argument is stored in a register.
    def register_arg? n
      n < @NREGISTER_ARGS
    end

    # 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.
    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

    # Restores the frame saved at the given location.
    # Requires @SAVE_FRAME_REGISTERS, an array of register names that
    # must be restored.
    def restore_frame frame
      restore_registers_from_frame frame, @SAVE_FRAME_REGISTERS
    end
    
    # Restores local variables from a saved frame.
    def restore_locals frame, *locals
      restore_registers_from_frame frame, registers_for_locals(locals)
    end

    # 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.
    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
    
    # 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.
    def save_frame frame
      registers_to_save = @SAVE_FRAME_REGISTERS -
        (@saved_registers & @LOCAL_REGISTERS)
      save_registers_to_frame frame, registers_to_save
    end

    # 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.
    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

    # Saves local variables to the given frame.
    # If no locals are specified, saves all locals.
    # If locals are specified, saves only the specified ones.
    def save_locals frame, *locals
      save_registers_to_frame frame, registers_for_locals(locals)
    end
    
    # 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.
    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

    # Returns the number of bytes necessary to save the current frame.
    def saved_frame_size
      @SAVED_FRAME_LAYOUT.length * @WORDSIZE
    end

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

    # Returns the name of the current section.
    # If a name is given, sets the name of the current section first.
    def section name = nil
      self.section = name if name
      @section
    end

    # Sets up _alias_name_ to refer to the same section as _original_name_.
    def section_alias alias_name, original_name
      @section_aliases[alias_name] = original_name
    end

    # Given n, returns the nearest multiple of @STACK_ALIGNMENT
    # that is >= n.
    def stack_align n
      (n + @STACK_ALIGNMENT - 1) / @STACK_ALIGNMENT * @STACK_ALIGNMENT
    end
    
    # Tests if a value is a substitution.
    def substitution? x
      x.respond_to?(:[]) && x[0] == :'%'
    end
    
    # Substitutes a numeric value for a given substitution key.
    def substitute_number key
      case key
      when :'saved-frame-size'
        saved_frame_size
      else
        @features[key].to_i
      end
    end
    
    # Tests if a value is a symbol.
    def symbol? value
      value.kind_of? Symbol
    end

    # 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).
    def symmetric_binop? op
      [:add, :and, :mul, :or, :xor].member? op
    end

    # Returns a set of symbols that have been used, but not defined.
    def undefined_symbols
      @symbol_tracker.used_but_undefined_symbols
    end

    # Executes a block of code, passing the block the name of +n+
    # unused temporary registers.
    #
    # Requires @TEMPORARIES, an array of temporary registers.
    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

    # Executes a block of code, passing the block the name of an unused
    # temporary register as its first argument.
    def with_temporary &block
      with_temporaries 1, &block
    end

    # Writes generated code to the given IO object.
    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

    # Used for scoping. Maintains a symbol table and keeps track of the number
    # of bytes that have been allocated on the stack.
    class Environment
      @@gensym_counter = 0

      attr_accessor :bytes, :offset
      attr_reader :args, :locals, :parent, :symbols

      # Creates a new environment.
      # If parent is specified, it will become the new environment's parent.
      # The new environment inherits all symbols from the parent environment.
      def initialize parent = nil
        ## Parent environment
        @parent = parent
        ## Symbol lookup table
        @symbols = parent ? parent.symbols.dup : {}
        ## Number of arguments
        @args = parent ? parent.args : 0
        ## Number of local variables
        @locals = parent ? parent.locals : 0
        ## Offset between base pointer and end of frame.
        @offset = parent ? parent.offset : 0
        ## Number of bytes allocated in this environment.
        @bytes = 0
      end

      # Adds symbol as an argument in this environment.
      # +info+ can be used by the code generator to store information it needs
      # about the symbol.
      def add_arg symbol, info = nil
        @symbols[symbol] = info
        @args = @args + 1
      end

      # Adds each of symbols to the arguments in
      # this environment.
      # Each entry in +symbols+ can be either a symbol,
      # or an array where the first element is the symbol and the second
      # element is extra information to be stored with the symbol.
      def add_args symbols
        symbols.each do |sym|
          if sym.respond_to? :[]
            add_arg *sym
          else
            add_arg sym
          end
        end
      end

      # Adds symbol as a local variable in this environment.
      def add_local symbol, info = nil
        @symbols[symbol] = info
        @locals = @locals + 1
      end

      # Adds each of symbols to the local variables in
      # this environment.
      # Each entry in +symbols+ can be either a symbol,
      # or an array where the first element is the symbol and the second
      # element is extra information to be stored with the symbol.
      def add_locals symbols
        symbols.each do |sym|
          if sym.respond_to? :[]
            add_local *sym
          else
            add_local sym
          end
        end
      end

      # Generates a new, unique symbol.
      def gensym
        Environment.gensym
      end

      # Looks up symbol in this environment.
      def [] symbol
        @symbols[symbol]
      end

      # Generates a new, unique symbol.
      def self.gensym
        @@gensym_counter = @@gensym_counter + 1
        "_G#{@@gensym_counter}".to_sym
      end

      # Returns an initial, top-level environment.
      def self.initial_environment
        Environment.new
      end
    end

    private

    # Returns the number of local variable slots required for the given
    # statements, given the current count and required number of slots.
    def count_locals_helper statements, count, max
      statements.each do |statement|
        case statement[0]
        when :ifeq, :ifge, :ifgt, :ifle, :iflt, :ifne
          max = count_locals_helper statement[2], count, max
          if statement.length > 3
            max = count_locals_helper statement[3], count, max
          end
        when :block
          max = count_locals_helper statement[1..-1], count, max
        when :let
          count = count + 1
          max = count if count > max
        end
      end
      max
    end

    # Given symbols, returns the set of symbols among those that
    # have been used without relocation.
    def symbols_used_unrelocated symbols
      symbols_set = symbols.kind_of?(Set) ? symbols : Set.new(symbols)
      new_symbols = symbols_set - @relocated_symbols
      @symbol_tracker.used_symbols & new_symbols      
    end
  end
end