lib/voodoo/generators/amd64_nasm_generator.rb

   1 require 'voodoo/generators/nasm_generator'
   2 require 'set'
   3
   4 module Voodoo
   5   # = AMD64 NASM Code Generator
   6   #
   7   # Code generator that emits NASM assembly code for AMD64 processors.
   8   #
   9   # == Calling Convention
  10   #
  11   # The calling convention implemented by this code generator is
  12   # compatible with the System V ABI for AMD64, provided that all
  13   # arguments are integers or pointers.
  14   #
  15   # Arguments are passed in registers. The registers are used in the
  16   # following order:
  17   #
  18   # 1. +rdi+
  19   # 2. +rsi+
  20   # 3. +rdx+
  21   # 4. +rcx+
  22   # 5. +r8+
  23   # 6. +r9+
  24   #
  25   # Additional arguments are pushed on the stack, starting with the last
  26   # argument and working backwards. These arguments are removed from the
  27   # stack by the caller, after the called function returns.
  28   #
  29   # The return value is passed in +rax+.
  30   #
  31   # For varargs functions, +rax+ must be set to an upper bound on the
  32   # number of vector arguments. Since the code generator does not know
  33   # whether the called function is a varargs function, this is always
  34   # done. Since the code generator never passes any vector arguments,
  35   # this means +rax+ is set to +0+ before each call.
  36   #
  37   # == Call Frames
  38   #
  39   #   arg_n
  40   #   :
  41   #   arg_7
  42   #   arg_6
  43   #   saved_rip
  44   #   saved_rbp <-- rbp
  45   #   arg_0
  46   #   arg_1
  47   #   :
  48   #   arg_5
  49   #   saved_r12
  50   #   :
  51   #   saved_r15
  52   #   local_4
  53   #   :
  54   #   local_n   <-- rsp
  55   #
  56   #
  57   # == Callee-Save Registers
  58   #
  59   # +rbp+, +rbx+, and +r12+ through +r15+ are callee-save registers.
  60   #
  61   # All other registers are caller-save.
  62   #
  63   class AMD64NasmGenerator < NasmGenerator
  64     def initialize params = {}
  65       # Number of bytes in a word
  66       @WORDSIZE_BITS = 3
  67       @WORDSIZE = 1 << @WORDSIZE_BITS
  68       # Word name in NASM lingo
  69       @WORD_NAME = 'qword'
  70       # Default alignment for code
  71       @CODE_ALIGNMENT = 0
  72       # Default alignment for data
  73       @DATA_ALIGNMENT = @WORDSIZE
  74       # Default alignment for functions
  75       @FUNCTION_ALIGNMENT = 16
  76       # Register used for return values
  77       @RETURN_REG = :rax
  78       # Register used as scratch register
  79       @SCRATCH_REG = :r11
  80       # Stack alignment restrictions
  81       @STACK_ALIGNMENT_BITS = @WORDSIZE_BITS
  82       @STACK_ALIGNMENT = 1 << @STACK_ALIGNMENT_BITS
  83       # Registers used for argument passing
  84       @ARG_REGS = [:rdi, :rsi, :rdx, :rcx, :r8, :r9]
  85       @NREG_ARGS = @ARG_REGS.length
  86       # Registers used to store locals
  87       @LOCAL_REGS = [:r12, :r13, :r14, :r15]
  88       @NLOCAL_REGS = @LOCAL_REGS.length
  89       @LOCAL_REGISTERS_SET = Set.new @LOCAL_REGS
  90       # Accumulator index
  91       @AX = :rax
  92       # Base index
  93       @BX = :rbx
  94       # Count index
  95       @CX = :rcx
  96       # Data index
  97       @DX = :rdx
  98       # Base pointer
  99       @BP = :rbp
 100       # Stack pointer
 101       @SP = :rsp
 102       @SAVED_FRAME_LAYOUT = {
 103         :rbx => 0, :r12 => 1, :r13 => 2, :r14 => 3, :r15 => 4,
 104         :rsp => 5, :rbp => 6,
 105       }
 106       @SAVE_FRAME_REGISTERS = @SAVED_FRAME_LAYOUT.keys
 107       super params
 108       @features.merge! \
 109         :'bits-per-word' => '64',
 110         :'byte-order' => 'little-endian',
 111         :'bytes-per-word' => '8'
 112       @saved_registers = []
 113       @function_end_label = nil
 114     end
 115
 116     #
 117     # == Data Definition
 118     #
 119
 120     # Define a machine word with the given value.
 121     def word value
 122       qword value
 123     end
 124
 125     #
 126     # == Functions
 127     #
 128
 129     # Emits function preamble and declare +formals+ as function arguments.
 130     def begin_function formals, nlocals
 131       environment = Environment.new @environment
 132       @saved_registers = []
 133       @environment = environment
 134       emit "push #{@BP}\nmov #{@BP}, #{@SP}\n"
 135       formals.each_with_index do |arg,i|
 136         @environment.add_arg arg, arg_offset(i)
 137         comment "# #{arg} is at #{offset_reference(@environment[arg])}"
 138         emit "push #{@ARG_REGS[i]}\n" if i < @NREG_ARGS
 139       end
 140       emit "sub #{@SP}, #{nlocals * @WORDSIZE}\n"
 141       number_of_register_locals(nlocals).times do |i|
 142         register = @LOCAL_REGS[i]
 143         ref = offset_reference saved_local_offset(i)
 144         emit "mov #{ref}, #{register}\n"
 145         @saved_registers << register
 146       end
 147       @function_end_label = gensym
 148     end
 149
 150     # Calls a function.
 151     def call func, *args
 152       # First couple of arguments go in registers
 153       register_args = args[0..(@NREG_ARGS - 1)] || []
 154       # Rest of arguments go on the stack
 155       stack_args = args[@NREG_ARGS..-1] || []
 156       # Push stack arguments
 157       stack_args.reverse.each { |arg| push_qword arg }
 158       # Load register arguments
 159       register_args.each_with_index do |arg,i|
 160         register = @ARG_REGS[i]
 161         value_ref = load_value arg, register
 162         if value_ref != register
 163           emit "mov #{register}, #{value_ref}\n"
 164         end
 165       end
 166       # Call function
 167       value_ref = load_value func, @SCRATCH_REG
 168       emit "xor rax, rax\n"
 169       # If value_ref is a symbol, use PLT-relative addressing
 170       if global?(func)
 171         emit "call #{value_ref} wrt ..plt\n"
 172       else
 173         emit "call #{value_ref}\n"
 174       end
 175       # Clean up stack
 176       unless stack_args.empty?
 177         emit "add rsp, #{stack_args.length * @WORDSIZE}\n"
 178       end
 179     end
 180
 181     # Ends a function body.
 182     def end_function
 183       label @function_end_label
 184       # Restore saved registers
 185       @saved_registers.each_with_index do |register,i|
 186         ref = offset_reference saved_local_offset(i)
 187         emit "mov #{register}, #{ref}\n"
 188       end
 189       # Destroy frame.
 190       emit "leave\n"
 191       # Return.
 192       emit "ret\n"
 193       if @environment == @top_level
 194         raise "Cannot end function when not in a function"
 195       else
 196         @environment = @top_level
 197       end
 198     end
 199
 200     # Returns from a function.
 201     def ret *words
 202       eval_expr words, @AX unless words.empty?
 203       goto @function_end_label
 204     end
 205
 206     # Calls a function, re-using the current call frame if possible.
 207     def tail_call func, *args
 208       # Compute required number of stack words
 209       nstackargs = number_of_stack_arguments args.length
 210       # If we need more stack arguments than we have now,
 211       # perform a normal call and return
 212       if nstackargs > number_of_stack_arguments(@environment.args)
 213         emit "; Not enough space for proper tail call; using regular call\n"
 214         ret :call, func, *args
 215       else
 216
 217         # If any arguments are going to be overwritten before they are
 218         # used, save them to new local variables and use those instead.
 219         (args.length - 1).downto(@NREG_ARGS) do |i|
 220           arg = args[i]
 221           next unless symbol?(arg)
 222           old_arg_offset = @environment[arg]
 223           next if old_arg_offset == nil || old_arg_offset < 0
 224           # arg is an argument that was passed on the stack.
 225           new_arg_offset = arg_offset i
 226           next unless old_arg_offset > new_arg_offset
 227           # arg will be overwritten before it is used.
 228           # Save it in a newly created temporary variable,
 229           # then use that instead.
 230           newsym = @environment.gensym
 231           let newsym, arg
 232           args[i] = newsym
 233         end
 234
 235         # Same for the function we will be calling.
 236         if symbol?(func)
 237           offset = @environment[func]
 238           if offset != nil && offset > 0
 239             newsym = @environment.gensym
 240             let newsym, func
 241             func = newsym
 242           end
 243         end
 244
 245         # Set stack arguments
 246         if args.length > @NREG_ARGS
 247           (args.length - 1).downto(@NREG_ARGS).each do |i|
 248             arg = args[i]
 249
 250             value_ref = load_value arg, @SCRATCH_REG
 251             newarg_ref = load_arg i
 252             # Elide code if source is same as destination
 253             unless value_ref == newarg_ref
 254               emit "mov #{@SCRATCH_REG}, #{value_ref}\n"
 255               emit "mov #{newarg_ref}, #{@SCRATCH_REG}\n"
 256             end
 257           end
 258         end
 259
 260         # Set register arguments
 261         number_of_register_arguments(args.length).times do |i|
 262           register = @ARG_REGS[i]
 263           load_value_into_register args[i], register
 264         end
 265
 266         # Tail call
 267         func_ref = load_value func, @BX
 268         emit "leave\n"
 269         set_register @AX, 0
 270         # If func_ref is a symbol, use PLT-relative addressing
 271         if global?(func)
 272           emit "jmp #{func_ref} wrt ..plt\n"
 273         else
 274           emit "jmp #{func_ref}\n"
 275         end
 276       end
 277     end
 278
 279     #
 280     # == Loading Values
 281     #
 282
 283     # Loads the value of the nth argument.
 284     def load_arg n, reg = @SCRATCH_REG
 285       if register_argument?(n)
 286         # Arguments that were originally passed in a register
 287         # are now below rbp
 288         "[rbp - #{(n + 1) * @WORDSIZE}]"
 289       else
 290         # Arguments that were originally passed on the stack
 291         # are now above rbp, starting 2 words above it
 292         "[rbp + #{(n + 2 - @NREG_ARGS) * @WORDSIZE}]"
 293       end
 294     end
 295
 296     #
 297     # == Miscellaneous
 298     #
 299
 300     # Returns the offset from rbp at which the nth argument is stored.
 301     def arg_offset n
 302       if n < @NREG_ARGS
 303         (n + 1) * -@WORDSIZE
 304       else
 305         (n - @NREG_ARGS) * @WORDSIZE + 2 * @WORDSIZE
 306       end
 307     end
 308
 309     # If the nth local is stored in a register, returns that register.
 310     # Otherwise, returns the offset from the frame pointer.
 311     def local_offset_or_register n
 312       if n < @NLOCAL_REGS
 313         @LOCAL_REGS[n]
 314       else
 315         (n + number_of_register_arguments + 1) * -@WORDSIZE
 316       end
 317     end
 318
 319     # Loads a value and push it on the stack.
 320     def push_qword value
 321       value_ref = load_value value, @SCRATCH_REG
 322       emit "push qword #{value_ref}\n"
 323     end
 324
 325     # Calculates the number of register arguments,
 326     # given the total number of arguments.
 327     def number_of_register_arguments n = @environment.args
 328       n < @NREG_ARGS ? n : @NREG_ARGS
 329     end
 330
 331     # Calculates the number of locals that are stored in registers.
 332     def number_of_register_locals n = @environment.locals
 333       n < @NLOCAL_REGS ? n : @NLOCAL_REGS
 334     end
 335
 336     # Calculates the number of stack arguments,
 337     # given the total number of arguments.
 338     def number_of_stack_arguments n = @environment.args
 339       x = n - @NREG_ARGS
 340       x < 0 ? 0 : x
 341     end
 342
 343     # Calculates the number of locals that are stored on the stack.
 344     def number_of_stack_locals n = @environment.locals
 345       x = n - @NLOCAL_REGS
 346       x < 0 ? 0 : x
 347     end
 348
 349     # Tests if the nth argument is a register argument.
 350     def register_argument? n
 351       n < number_of_register_arguments
 352     end
 353
 354     # Returns the offset of the nth saved local.
 355     def saved_local_offset n
 356       (number_of_register_arguments + n + 1) * -@WORDSIZE
 357     end
 358
 359   end
 360
 361   # Register class
 362   Voodoo::CodeGenerator.register_generator AMD64NasmGenerator,
 363                                            :architecture => :amd64,
 364                                            :format => :nasm
 365 end