src/compiler/lopcodes.lua

   1 ----------------------------------------------------------------------
   2 --
   3 -- WARNING! You're entering a hackish area, proceed at your own risks!
   4 --
   5 -- This code results from the borrowing, then ruthless abuse, of
   6 -- Yueliang's implementation of Lua 5.0 compiler. I claim
   7 -- responsibility for all of the ugly, dirty stuff that you might spot
   8 -- in it.
   9 --
  10 -- Eventually, this code will be rewritten, either in Lua or more
  11 -- probably in C. Meanwhile, if you're interested into digging
  12 -- metalua's sources, this is not the best part to invest your time
  13 -- on.
  14 --
  15 -- End of warning.
  16 --
  17 ----------------------------------------------------------------------
  18
  19 --[[--------------------------------------------------------------------
  20
  21   $Id$
  22
  23   lopcodes.lua
  24   Lua 5 virtual machine opcodes in Lua
  25   This file is part of Yueliang.
  26
  27   Copyright (c) 2005 Kein-Hong Man <khman@users.sf.net>
  28   The COPYRIGHT file describes the conditions
  29   under which this software may be distributed.
  30
  31   See the ChangeLog for more information.
  32
  33 ------------------------------------------------------------------------
  34
  35   [FF] Slightly modified, mainly to produce Lua 5.1 bytecode.
  36
  37 ----------------------------------------------------------------------]]
  38
  39 --[[--------------------------------------------------------------------
  40 -- Notes:
  41 -- * an Instruction is a table with OP, A, B, C, Bx elements; this
  42 --   should allow instruction handling to work with doubles and ints
  43 -- * Added:
  44 --   luaP:Instruction(i): convert field elements to a 4-char string
  45 --   luaP:DecodeInst(x): convert 4-char string into field elements
  46 -- * WARNING luaP:Instruction outputs instructions encoded in little-
  47 --   endian form and field size and positions are hard-coded
  48 ----------------------------------------------------------------------]]
  49
  50 module("bytecode", package.seeall)
  51
  52 local function debugf() end
  53
  54 luaP = { }
  55
  56 --[[
  57 ===========================================================================
  58   We assume that instructions are unsigned numbers.
  59   All instructions have an opcode in the first 6 bits.
  60   Instructions can have the following fields:
  61         'A' : 8 bits
  62         'B' : 9 bits
  63         'C' : 9 bits
  64         'Bx' : 18 bits ('B' and 'C' together)
  65         'sBx' : signed Bx
  66
  67   A signed argument is represented in excess K; that is, the number
  68   value is the unsigned value minus K. K is exactly the maximum value
  69   for that argument (so that -max is represented by 0, and +max is
  70   represented by 2*max), which is half the maximum for the corresponding
  71   unsigned argument.
  72 ===========================================================================
  73 --]]
  74
  75 luaP.OpMode = {"iABC", "iABx", "iAsBx"}  -- basic instruction format
  76
  77 ------------------------------------------------------------------------
  78 -- size and position of opcode arguments.
  79 -- * WARNING size and position is hard-coded elsewhere in this script
  80 ------------------------------------------------------------------------
  81 luaP.SIZE_C  = 9
  82 luaP.SIZE_B  = 9
  83 luaP.SIZE_Bx = luaP.SIZE_C + luaP.SIZE_B
  84 luaP.SIZE_A  = 8
  85
  86 luaP.SIZE_OP = 6
  87
  88 luaP.POS_C  = luaP.SIZE_OP
  89 luaP.POS_B  = luaP.POS_C + luaP.SIZE_C
  90 luaP.POS_Bx = luaP.POS_C
  91 luaP.POS_A  = luaP.POS_B + luaP.SIZE_B
  92
  93 --FF from 5.1
  94 luaP.BITRK = 2^(luaP.SIZE_B - 1)
  95 function luaP:ISK(x) return x >= self.BITRK end
  96 luaP.MAXINDEXRK = luaP.BITRK - 1
  97 function luaP:RKASK(x)
  98    if x < self.BITRK then return x+self.BITRK else return x end
  99 end
 100
 101
 102
 103 ------------------------------------------------------------------------
 104 -- limits for opcode arguments.
 105 -- we use (signed) int to manipulate most arguments,
 106 -- so they must fit in BITS_INT-1 bits (-1 for sign)
 107 ------------------------------------------------------------------------
 108 -- removed "#if SIZE_Bx < BITS_INT-1" test, assume this script is
 109 -- running on a Lua VM with double or int as LUA_NUMBER
 110
 111 luaP.MAXARG_Bx  = math.ldexp(1, luaP.SIZE_Bx) - 1
 112 luaP.MAXARG_sBx = math.floor(luaP.MAXARG_Bx / 2)  -- 'sBx' is signed
 113
 114 luaP.MAXARG_A = math.ldexp(1, luaP.SIZE_A) - 1
 115 luaP.MAXARG_B = math.ldexp(1, luaP.SIZE_B) - 1
 116 luaP.MAXARG_C = math.ldexp(1, luaP.SIZE_C) - 1
 117
 118 -- creates a mask with 'n' 1 bits at position 'p'
 119 -- MASK1(n,p) deleted
 120 -- creates a mask with 'n' 0 bits at position 'p'
 121 -- MASK0(n,p) deleted
 122
 123 --[[--------------------------------------------------------------------
 124   Visual representation for reference:
 125
 126    31     |     |     |          0      bit position
 127     +-----+-----+-----+----------+
 128     |  B  |  C  |  A  |  Opcode  |      iABC format
 129     +-----+-----+-----+----------+
 130     -  9  -  9  -  8  -    6     -      field sizes
 131     +-----+-----+-----+----------+
 132     |   [s]Bx   |  A  |  Opcode  |      iABx | iAsBx format
 133     +-----+-----+-----+----------+
 134 ----------------------------------------------------------------------]]
 135
 136 ------------------------------------------------------------------------
 137 -- the following macros help to manipulate instructions
 138 -- * changed to a table object representation, very clean compared to
 139 --   the [nightmare] alternatives of using a number or a string
 140 ------------------------------------------------------------------------
 141
 142 -- these accept or return opcodes in the form of string names
 143 function luaP:GET_OPCODE(i) return self.ROpCode[i.OP] end
 144 function luaP:SET_OPCODE(i, o) i.OP = self.OpCode[o] end
 145
 146 function luaP:GETARG_A(i) return i.A end
 147 function luaP:SETARG_A(i, u) i.A = u end
 148
 149 function luaP:GETARG_B(i) return i.B end
 150 function luaP:SETARG_B(i, b) i.B = b end
 151
 152 function luaP:GETARG_C(i) return i.C end
 153 function luaP:SETARG_C(i, b) i.C = b end
 154
 155 function luaP:GETARG_Bx(i) return i.Bx end
 156 function luaP:SETARG_Bx(i, b) i.Bx = b end
 157
 158 function luaP:GETARG_sBx(i) return i.Bx - self.MAXARG_sBx end
 159 function luaP:SETARG_sBx(i, b) i.Bx = b + self.MAXARG_sBx end
 160
 161 function luaP:CREATE_ABC(o,a,b,c)
 162   return {OP = self.OpCode[o], A = a, B = b, C = c}
 163 end
 164
 165 function luaP:CREATE_ABx(o,a,bc)
 166   return {OP = self.OpCode[o], A = a, Bx = bc}
 167 end
 168
 169 ------------------------------------------------------------------------
 170 -- Bit shuffling stuffs
 171 ------------------------------------------------------------------------
 172
 173 if false and pcall (require, 'bit') then
 174    ------------------------------------------------------------------------
 175    -- Return a 4-char string little-endian encoded form of an instruction
 176    ------------------------------------------------------------------------
 177    function luaP:Instruction(i)
 178       --FIXME
 179    end
 180 else
 181    ------------------------------------------------------------------------
 182    -- Version without bit manipulation library.
 183    ------------------------------------------------------------------------
 184    local p2 = {1,2,4,8,16,32,64,128,256, 512, 1024, 2048, 4096}
 185    -- keeps [n] bits from [x]
 186    local function keep (x, n) return x % p2[n+1] end
 187    -- shifts bits of [x] [n] places to the right
 188    local function srb (x,n) return math.floor (x / p2[n+1]) end
 189    -- shifts bits of [x] [n] places to the left
 190    local function slb (x,n) return x * p2[n+1] end
 191
 192    ------------------------------------------------------------------------
 193    -- Return a 4-char string little-endian encoded form of an instruction
 194    ------------------------------------------------------------------------
 195    function luaP:Instruction(i)
 196       -- printf("Instr->string: %s %s", self.opnames[i.OP], table.tostring(i))
 197       local c0, c1, c2, c3
 198       -- change to OP/A/B/C format if needed
 199       if i.Bx then i.C = keep (i.Bx, 9); i.B = srb (i.Bx, 9) end
 200       -- c0 = 6B from opcode + 2LSB from A (flushed to MSB)
 201       c0 = i.OP + slb (keep (i.A, 2), 6)
 202       -- c1 = 6MSB from A + 2LSB from C (flushed to MSB)
 203       c1 = srb (i.A, 2) + slb (keep (i.C, 2), 6)
 204       -- c2 = 7MSB from C + 1LSB from B (flushed to MSB)
 205       c2 = srb (i.C, 2) + slb (keep (i.B, 1), 7)
 206       -- c3 = 8MSB from B
 207       c3 = srb (i.B, 1)
 208       --printf ("Instruction:   %s %s", self.opnames[i.OP], tostringv (i))
 209       --printf ("Bin encoding:  %x %x %x %x", c0, c1, c2, c3)
 210       return string.char(c0, c1, c2, c3)
 211    end
 212 end
 213 ------------------------------------------------------------------------
 214 -- decodes a 4-char little-endian string into an instruction struct
 215 ------------------------------------------------------------------------
 216 function luaP:DecodeInst(x)
 217   error "Not implemented"
 218 end
 219
 220 ------------------------------------------------------------------------
 221 -- invalid register that fits in 8 bits
 222 ------------------------------------------------------------------------
 223 luaP.NO_REG = luaP.MAXARG_A
 224
 225 ------------------------------------------------------------------------
 226 -- R(x) - register
 227 -- Kst(x) - constant (in constant table)
 228 -- RK(x) == if x < MAXSTACK then R(x) else Kst(x-MAXSTACK)
 229 ------------------------------------------------------------------------
 230
 231 ------------------------------------------------------------------------
 232 -- grep "ORDER OP" if you change these enums
 233 ------------------------------------------------------------------------
 234
 235 --[[--------------------------------------------------------------------
 236 Lua virtual machine opcodes (enum OpCode):
 237 ------------------------------------------------------------------------
 238 name          args    description
 239 ------------------------------------------------------------------------
 240 OP_MOVE       A B     R(A) := R(B)
 241 OP_LOADK      A Bx    R(A) := Kst(Bx)
 242 OP_LOADBOOL   A B C   R(A) := (Bool)B; if (C) PC++
 243 OP_LOADNIL    A B     R(A) := ... := R(B) := nil
 244 OP_GETUPVAL   A B     R(A) := UpValue[B]
 245 OP_GETGLOBAL  A Bx    R(A) := Gbl[Kst(Bx)]
 246 OP_GETTABLE   A B C   R(A) := R(B)[RK(C)]
 247 OP_SETGLOBAL  A Bx    Gbl[Kst(Bx)] := R(A)
 248 OP_SETUPVAL   A B     UpValue[B] := R(A)
 249 OP_SETTABLE   A B C   R(A)[RK(B)] := RK(C)
 250 OP_NEWTABLE   A B C   R(A) := {} (size = B,C)
 251 OP_SELF       A B C   R(A+1) := R(B); R(A) := R(B)[RK(C)]
 252 OP_ADD        A B C   R(A) := RK(B) + RK(C)
 253 OP_SUB        A B C   R(A) := RK(B) - RK(C)
 254 OP_MUL        A B C   R(A) := RK(B) * RK(C)
 255 OP_DIV        A B C   R(A) := RK(B) / RK(C)
 256 OP_POW        A B C   R(A) := RK(B) ^ RK(C)
 257 OP_UNM        A B     R(A) := -R(B)
 258 OP_NOT        A B     R(A) := not R(B)
 259 OP_CONCAT     A B C   R(A) := R(B).. ... ..R(C)
 260 OP_JMP        sBx     PC += sBx
 261 OP_EQ         A B C   if ((RK(B) == RK(C)) ~= A) then pc++
 262 OP_LT         A B C   if ((RK(B) <  RK(C)) ~= A) then pc++
 263 OP_LE         A B C   if ((RK(B) <= RK(C)) ~= A) then pc++
 264 OP_TEST       A B C   if (R(B) <=> C) then R(A) := R(B) else pc++
 265 OP_CALL       A B C   R(A), ... ,R(A+C-2) := R(A)(R(A+1), ... ,R(A+B-1))
 266 OP_TAILCALL   A B C   return R(A)(R(A+1), ... ,R(A+B-1))
 267 OP_RETURN     A B     return R(A), ... ,R(A+B-2)  (see note)
 268 OP_FORLOOP    A sBx   R(A)+=R(A+2); if R(A) <?= R(A+1) then PC+= sBx
 269 OP_TFORLOOP   A C     R(A+2), ... ,R(A+2+C) := R(A)(R(A+1), R(A+2));
 270                       if R(A+2) ~= nil then pc++
 271 OP_TFORPREP   A sBx   if type(R(A)) == table then R(A+1):=R(A), R(A):=next;
 272                       PC += sBx
 273 OP_SETLIST    A Bx    R(A)[Bx-Bx%FPF+i] := R(A+i), 1 <= i <= Bx%FPF+1
 274 OP_SETLISTO   A Bx    (see note)
 275 OP_CLOSE      A       close all variables in the stack up to (>=) R(A)
 276 OP_CLOSURE    A Bx    R(A) := closure(KPROTO[Bx], R(A), ... ,R(A+n))
 277 ----------------------------------------------------------------------]]
 278
 279 luaP.opnames = {}  -- opcode names
 280 luaP.OpCode = {}   -- lookup name -> number
 281 luaP.ROpCode = {}  -- lookup number -> name
 282
 283 local i = 0
 284 for v in string.gfind([[
 285 MOVE -- 0
 286 LOADK
 287 LOADBOOL
 288 LOADNIL
 289 GETUPVAL
 290 GETGLOBAL -- 5
 291 GETTABLE
 292 SETGLOBAL
 293 SETUPVAL
 294 SETTABLE
 295 NEWTABLE -- 10
 296 SELF
 297 ADD
 298 SUB
 299 MUL
 300 DIV -- 15
 301 MOD
 302 POW
 303 UNM
 304 NOT
 305 LEN -- 20
 306 CONCAT
 307 JMP
 308 EQ
 309 LT
 310 LE -- 25
 311 TEST
 312 TESTSET
 313 CALL
 314 TAILCALL
 315 RETURN -- 30
 316 FORLOOP
 317 FORPREP
 318 TFORLOOP
 319 SETLIST
 320 CLOSE -- 35
 321 CLOSURE
 322 VARARG
 323 ]], "[%a]+") do
 324   local n = "OP_"..v
 325   luaP.opnames[i] = v
 326   luaP.OpCode[n] = i
 327   luaP.ROpCode[i] = n
 328   i = i + 1
 329 end
 330 luaP.NUM_OPCODES = i
 331
 332 --[[
 333 ===========================================================================
 334   Notes:
 335   (1) In OP_CALL, if (B == 0) then B = top. C is the number of returns - 1,
 336       and can be 0: OP_CALL then sets 'top' to last_result+1, so
 337       next open instruction (OP_CALL, OP_RETURN, OP_SETLIST) may use 'top'.
 338
 339   (2) In OP_RETURN, if (B == 0) then return up to 'top'
 340
 341   (3) For comparisons, B specifies what conditions the test should accept.
 342
 343   (4) All 'skips' (pc++) assume that next instruction is a jump
 344
 345   (5) OP_SETLISTO is used when the last item in a table constructor is a
 346       function, so the number of elements set is up to top of stack
 347 ===========================================================================
 348 --]]
 349
 350 ------------------------------------------------------------------------
 351 -- masks for instruction properties
 352 ------------------------------------------------------------------------
 353 -- was enum OpModeMask:
 354 luaP.OpModeBreg = 2  -- B is a register
 355 luaP.OpModeBrk  = 3  -- B is a register/constant
 356 luaP.OpModeCrk  = 4  -- C is a register/constant
 357 luaP.OpModesetA = 5  -- instruction set register A
 358 luaP.OpModeK    = 6  -- Bx is a constant
 359 luaP.OpModeT    = 1  -- operator is a test
 360
 361 ------------------------------------------------------------------------
 362 -- get opcode mode, e.g. "iABC"
 363 ------------------------------------------------------------------------
 364 function luaP:getOpMode(m)
 365    --printv(m)
 366    --printv(self.OpCode[m])
 367    --printv(self.opmodes [self.OpCode[m]+1])
 368    return self.OpMode[tonumber(string.sub(self.opmodes[self.OpCode[m] + 1], 7, 7))]
 369 end
 370
 371 ------------------------------------------------------------------------
 372 -- test an instruction property flag
 373 -- * b is a string, e.g. "OpModeBreg"
 374 ------------------------------------------------------------------------
 375 function luaP:testOpMode(m, b)
 376   return (string.sub(self.opmodes[self.OpCode[m] + 1], self[b], self[b]) == "1")
 377 end
 378
 379 -- number of list items to accumulate before a SETLIST instruction
 380 -- (must be a power of 2)
 381 -- * used in lparser, lvm, ldebug, ltests
 382 luaP.LFIELDS_PER_FLUSH = 50 --FF updated to match 5.1
 383
 384 -- luaP_opnames[] is set above, as the luaP.opnames table
 385 -- opmode(t,b,bk,ck,sa,k,m) deleted
 386
 387 --[[--------------------------------------------------------------------
 388   Legend for luaP:opmodes:
 389   1 T  -> T (is a test?)
 390   2 B  -> B is a register
 391   3 b  -> B is an RK register/constant combination
 392   4 C  -> C is an RK register/constant combination
 393   5 A  -> register A is set by the opcode
 394   6 K  -> Bx is a constant
 395   7 m  -> 1 if iABC  layout,
 396           2 if iABx  layout,
 397           3 if iAsBx layout
 398 ----------------------------------------------------------------------]]
 399
 400 luaP.opmodes = {
 401 -- TBbCAKm      opcode
 402   "0100101", -- OP_MOVE      0
 403   "0000112", -- OP_LOADK
 404   "0000101", -- OP_LOADBOOL
 405   "0100101", -- OP_LOADNIL
 406   "0000101", -- OP_GETUPVAL
 407   "0000112", -- OP_GETGLOBAL 5
 408   "0101101", -- OP_GETTABLE
 409   "0000012", -- OP_SETGLOBAL
 410   "0000001", -- OP_SETUPVAL
 411   "0011001", -- OP_SETTABLE
 412   "0000101", -- OP_NEWTABLE 10
 413   "0101101", -- OP_SELF
 414   "0011101", -- OP_ADD
 415   "0011101", -- OP_SUB
 416   "0011101", -- OP_MUL
 417   "0011101", -- OP_DIV      15
 418   "0011101", -- OP_MOD
 419   "0011101", -- OP_POW
 420   "0100101", -- OP_UNM
 421   "0100101", -- OP_NOT
 422   "0100101", -- OP_LEN      20
 423   "0101101", -- OP_CONCAT
 424   "0000003", -- OP_JMP
 425   "1011001", -- OP_EQ
 426   "1011001", -- OP_LT
 427   "1011001", -- OP_LE       25
 428   "1000101", -- OP_TEST
 429   "1100101", -- OP_TESTSET
 430   "0000001", -- OP_CALL
 431   "0000001", -- OP_TAILCALL
 432   "0000001", -- OP_RETURN   30
 433   "0000003", -- OP_FORLOOP
 434   "0000103", -- OP_FORPREP
 435   "1000101", -- OP_TFORLOOP
 436   "0000001", -- OP_SETLIST
 437   "0000001", -- OP_CLOSE    35
 438   "0000102", -- OP_CLOSURE
 439   "0000101"  -- OP_VARARG
 440 }