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           emit "call #{value_ref} wrt ..plt\n"
 170         else
 171           emit "call #{value_ref}\n"
 172         end
 173       end
 174       # Clean up stack
 175       unless stack_args.empty?
 176         emit "add rsp, #{stack_args.length * @WORDSIZE}\n"
 177       end
 178     end
 179
 180     # Ends a function body.
 181     def end_function
 182       label @function_end_label
 183       # Restore saved registers
 184       @saved_registers.each_with_index do |register,i|
 185         ref = offset_reference saved_local_offset(i)
 186         emit "mov #{register}, #{ref}\n"
 187       end
 188       # Destroy frame.
 189       emit "leave\n"
 190       # Return.
 191       emit "ret\n"
 192       if @environment == @top_level
 193         raise "Cannot end function when not in a function"
 194       else
 195         @environment = @top_level
 196       end
 197     end
 198
 199     # Returns from a function.
 200     def ret *words
 201       eval_expr words, @AX unless words.empty?
 202       goto @function_end_label
 203     end
 204
 205     # Calls a function, re-using the current call frame if possible.
 206     def tail_call func, *args
 207       # Compute required number of stack words
 208       nstackargs = number_of_stack_arguments args.length
 209       # If we need more stack arguments than we have now,
 210       # perform a normal call and return
 211       if nstackargs > number_of_stack_arguments(@environment.args)
 212         emit "; Not enough space for proper tail call; using regular call\n"
 213         ret :call, func, *args
 214       else
 215
 216         # If any arguments are going to be overwritten before they are
 217         # used, save them to new local variables and use those instead.
 218         (args.length - 1).downto(@NREG_ARGS) do |i|
 219           arg = args[i]
 220           next unless symbol?(arg)
 221           old_arg_offset = @environment[arg]
 222           next if old_arg_offset == nil || old_arg_offset < 0
 223           # arg is an argument that was passed on the stack.
 224           new_arg_offset = arg_offset i
 225           next unless old_arg_offset > new_arg_offset
 226           # arg will be overwritten before it is used.
 227           # Save it in a newly created temporary variable,
 228           # then use that instead.
 229           newsym = @environment.gensym
 230           let newsym, arg
 231           args[i] = newsym
 232         end
 233
 234         # Same for the function we will be calling.
 235         if symbol?(func)
 236           offset = @environment[func]
 237           if offset != nil && offset > 0
 238             newsym = @environment.gensym
 239             let newsym, func
 240             func = newsym
 241           end
 242         end
 243
 244         # Set stack arguments
 245         if args.length > @NREG_ARGS
 246           (args.length - 1).downto(@NREG_ARGS).each do |i|
 247             arg = args[i]
 248
 249             with_temporary do |temporary|
 250               value_ref = load_value arg, temporary
 251               newarg_ref = load_arg i
 252               # Elide code if source is same as destination
 253               unless value_ref == newarg_ref
 254                 emit "mov #{temporary}, #{value_ref}\n"
 255                 emit "mov #{newarg_ref}, #{temporary}\n"
 256               end
 257             end
 258           end
 259         end
 260
 261         # Set register arguments
 262         number_of_register_arguments(args.length).times do |i|
 263           register = @ARG_REGS[i]
 264           load_value_into_register args[i], register
 265         end
 266
 267         # Tail call
 268         func_ref = load_value func, @BX
 269         emit "leave\n"
 270         set_register @AX, 0
 271         # If func_ref is a symbol, use PLT-relative addressing
 272         if global?(func)
 273           emit "jmp #{func_ref} wrt ..plt\n"
 274         else
 275           emit "jmp #{func_ref}\n"
 276         end
 277       end
 278     end
 279
 280     #
 281     # == Loading Values
 282     #
 283
 284     # Loads the value of the nth argument.
 285     def load_arg n
 286       if register_argument?(n)
 287         # Arguments that were originally passed in a register
 288         # are now below rbp
 289         "[rbp - #{(n + 1) * @WORDSIZE}]"
 290       else
 291         # Arguments that were originally passed on the stack
 292         # are now above rbp, starting 2 words above it
 293         "[rbp + #{(n + 2 - @NREG_ARGS) * @WORDSIZE}]"
 294       end
 295     end
 296
 297     #
 298     # == Miscellaneous
 299     #
 300
 301     # Returns the offset from rbp at which the nth argument is stored.
 302     def arg_offset n
 303       if n < @NREG_ARGS
 304         (n + 1) * -@WORDSIZE
 305       else
 306         (n - @NREG_ARGS) * @WORDSIZE + 2 * @WORDSIZE
 307       end
 308     end
 309
 310     # If the nth local is stored in a register, returns that register.
 311     # Otherwise, returns the offset from the frame pointer.
 312     def local_offset_or_register n
 313       if n < @NLOCAL_REGISTERS
 314         @LOCAL_REGISTERS[n]
 315       else
 316         (n + number_of_register_arguments + 1) * -@WORDSIZE
 317       end
 318     end
 319
 320     # Loads a value and push it on the stack.
 321     def push_qword value
 322       with_temporary do |temporary|
 323         value_ref = load_value value, temporary
 324         emit "push qword #{value_ref}\n"
 325       end
 326     end
 327
 328     # Calculates the number of register arguments,
 329     # given the total number of arguments.
 330     def number_of_register_arguments n = @environment.args
 331       n < @NREG_ARGS ? n : @NREG_ARGS
 332     end
 333
 334     # Calculates the number of locals that are stored in registers.
 335     def number_of_register_locals n = @environment.locals
 336       n < @NLOCAL_REGISTERS ? n : @NLOCAL_REGISTERS
 337     end
 338
 339     # Calculates the number of stack arguments,
 340     # given the total number of arguments.
 341     def number_of_stack_arguments n = @environment.args
 342       x = n - @NREG_ARGS
 343       x < 0 ? 0 : x
 344     end
 345
 346     # Calculates the number of locals that are stored on the stack.
 347     def number_of_stack_locals n = @environment.locals
 348       x = n - @NLOCAL_REGISTERS
 349       x < 0 ? 0 : x
 350     end
 351
 352     # Tests if the nth argument is a register argument.
 353     def register_argument? n
 354       n < number_of_register_arguments
 355     end
 356
 357     # Returns the offset of the nth saved local.
 358     def saved_local_offset n
 359       (number_of_register_arguments + n + 1) * -@WORDSIZE
 360     end
 361
 362   end
 363
 364   # Register class
 365   Voodoo::CodeGenerator.register_generator AMD64NasmGenerator,
 366                                            :architecture => :amd64,
 367                                            :format => :nasm
 368 end