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       # Stack alignment restrictions
  79       @STACK_ALIGNMENT_BITS = @WORDSIZE_BITS
  80       @STACK_ALIGNMENT = 1 << @STACK_ALIGNMENT_BITS
  81       @TEMPORARIES = [:r11]
  82       # Registers used for argument passing
  83       @ARG_REGS = [:rdi, :rsi, :rdx, :rcx, :r8, :r9]
  84       @NREG_ARGS = @ARG_REGS.length
  85       # Registers used to store locals
  86       @LOCAL_REGISTERS = [:r12, :r13, :r14, :r15]
  87       @NLOCAL_REGISTERS = @LOCAL_REGISTERS.length
  88       @LOCAL_REGISTERS_SET = Set.new @LOCAL_REGISTERS
  89       # Accumulator index
  90       @AX = :rax
  91       # Base index
  92       @BX = :rbx
  93       # Count index
  94       @CX = :rcx
  95       # Data index
  96       @DX = :rdx
  97       # Base pointer
  98       @BP = :rbp
  99       # Stack pointer
 100       @SP = :rsp
 101       @SAVE_FRAME_REGISTERS = [:rbx, :r12, :r13, :r14, :r15, :rsp, :rbp]
 102       @SAVED_FRAME_LAYOUT = {}
 103       @SAVE_FRAME_REGISTERS.each_with_index { |r,i| @SAVED_FRAME_LAYOUT[r] = i }
 104       super params
 105       @features.merge! \
 106         :'bits-per-word' => '64',
 107         :'byte-order' => 'little-endian',
 108         :'bytes-per-word' => '8'
 109       @saved_registers = []
 110       @function_end_label = nil
 111     end
 112
 113     #
 114     # == Data Definition
 115     #
 116
 117     # Define a machine word with the given value.
 118     def word value
 119       qword value
 120     end
 121
 122     #
 123     # == Functions
 124     #
 125
 126     # Emits function preamble and declare +formals+ as function arguments.
 127     def begin_function formals, nlocals
 128       environment = Environment.new @environment
 129       @saved_registers = []
 130       @environment = environment
 131       emit "push #{@BP}\nmov #{@BP}, #{@SP}\n"
 132       formals.each_with_index do |arg,i|
 133         @environment.add_arg arg, arg_offset(i)
 134         comment "# #{arg} is at #{offset_reference(@environment[arg])}"
 135         emit "push #{@ARG_REGS[i]}\n" if i < @NREG_ARGS
 136       end
 137       emit "sub #{@SP}, #{nlocals * @WORDSIZE}\n"
 138       number_of_register_locals(nlocals).times do |i|
 139         register = @LOCAL_REGISTERS[i]
 140         ref = offset_reference saved_local_offset(i)
 141         emit "mov #{ref}, #{register}\n"
 142         @saved_registers << register
 143       end
 144       @function_end_label = gensym
 145     end
 146
 147     # Calls a function.
 148     def call func, *args
 149       # First couple of arguments go in registers
 150       register_args = args[0..(@NREG_ARGS - 1)] || []
 151       # Rest of arguments go on the stack
 152       stack_args = args[@NREG_ARGS..-1] || []
 153       # Push stack arguments
 154       stack_args.reverse.each { |arg| push_qword arg }
 155       # Load register arguments
 156       register_args.each_with_index do |arg,i|
 157         register = @ARG_REGS[i]
 158         value_ref = load_value arg, register
 159         if value_ref != register
 160           emit "mov #{register}, #{value_ref}\n"
 161         end
 162       end
 163       # Call function
 164       with_temporary do |temporary|
 165         value_ref = load_value func, temporary
 166         emit "xor rax, rax\n"
 167         # If value_ref is a symbol, use PLT-relative addressing
 168         if global?(func)
 169           @symbol_tracker.use func
 170           emit "call #{value_ref} wrt ..plt\n"
 171         else
 172           emit "call #{value_ref}\n"
 173         end
 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             with_temporary do |temporary|
 251               value_ref = load_value arg, temporary
 252               newarg_ref = load_arg i
 253               # Elide code if source is same as destination
 254               unless value_ref == newarg_ref
 255                 emit "mov #{temporary}, #{value_ref}\n"
 256                 emit "mov #{newarg_ref}, #{temporary}\n"
 257               end
 258             end
 259           end
 260         end
 261
 262         # Set register arguments
 263         number_of_register_arguments(args.length).times do |i|
 264           register = @ARG_REGS[i]
 265           load_value_into_register args[i], register
 266         end
 267
 268         # Tail call
 269         func_ref = load_value func, @BX
 270         emit "leave\n"
 271         set_register @AX, 0
 272         # If func_ref is a symbol, use PLT-relative addressing
 273         if global?(func)
 274           emit "jmp #{func_ref} wrt ..plt\n"
 275         else
 276           emit "jmp #{func_ref}\n"
 277         end
 278       end
 279     end
 280
 281     #
 282     # == Loading Values
 283     #
 284
 285     # Loads the value of the nth argument.
 286     def load_arg n
 287       if register_argument?(n)
 288         # Arguments that were originally passed in a register
 289         # are now below rbp
 290         "[rbp - #{(n + 1) * @WORDSIZE}]"
 291       else
 292         # Arguments that were originally passed on the stack
 293         # are now above rbp, starting 2 words above it
 294         "[rbp + #{(n + 2 - @NREG_ARGS) * @WORDSIZE}]"
 295       end
 296     end
 297
 298     # Loads a symbol from the global offset table.
 299     def load_symbol_from_got symbol, reg
 300       "[rel #{symbol} wrt ..gotpc]"
 301     end
 302
 303     #
 304     # == Miscellaneous
 305     #
 306
 307     # Returns the offset from rbp at which the nth argument is stored.
 308     def arg_offset n
 309       if n < @NREG_ARGS
 310         (n + 1) * -@WORDSIZE
 311       else
 312         (n - @NREG_ARGS) * @WORDSIZE + 2 * @WORDSIZE
 313       end
 314     end
 315
 316     # If the nth local is stored in a register, returns that register.
 317     # Otherwise, returns the offset from the frame pointer.
 318     def local_offset_or_register n
 319       if n < @NLOCAL_REGISTERS
 320         @LOCAL_REGISTERS[n]
 321       else
 322         (n + number_of_register_arguments + 1) * -@WORDSIZE
 323       end
 324     end
 325
 326     # Loads a value and push it on the stack.
 327     def push_qword value
 328       with_temporary do |temporary|
 329         value_ref = load_value value, temporary
 330         emit "push qword #{value_ref}\n"
 331       end
 332     end
 333
 334     # Calculates the number of register arguments,
 335     # given the total number of arguments.
 336     def number_of_register_arguments n = @environment.args
 337       n < @NREG_ARGS ? n : @NREG_ARGS
 338     end
 339
 340     # Calculates the number of locals that are stored in registers.
 341     def number_of_register_locals n = @environment.locals
 342       n < @NLOCAL_REGISTERS ? n : @NLOCAL_REGISTERS
 343     end
 344
 345     # Calculates the number of stack arguments,
 346     # given the total number of arguments.
 347     def number_of_stack_arguments n = @environment.args
 348       x = n - @NREG_ARGS
 349       x < 0 ? 0 : x
 350     end
 351
 352     # Calculates the number of locals that are stored on the stack.
 353     def number_of_stack_locals n = @environment.locals
 354       x = n - @NLOCAL_REGISTERS
 355       x < 0 ? 0 : x
 356     end
 357
 358     # Tests if the nth argument is a register argument.
 359     def register_argument? n
 360       n < number_of_register_arguments
 361     end
 362
 363     # Returns the offset of the nth saved local.
 364     def saved_local_offset n
 365       (number_of_register_arguments + n + 1) * -@WORDSIZE
 366     end
 367
 368   end
 369
 370   # Register class
 371   Voodoo::CodeGenerator.register_generator AMD64NasmGenerator,
 372                                            :architecture => :amd64,
 373                                            :format => :nasm
 374 end