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