src/lj_jit.h

   1 /*
   2 ** Common definitions for the JIT compiler.
   3 ** Copyright (C) 2005-2011 Mike Pall. See Copyright Notice in luajit.h
   4 */
   5
   6 #ifndef _LJ_JIT_H
   7 #define _LJ_JIT_H
   8
   9 #include "lj_obj.h"
  10 #include "lj_ir.h"
  11
  12 /* JIT engine flags. */
  13 #define JIT_F_ON                0x00000001
  14
  15 /* CPU-specific JIT engine flags. */
  16 #if LJ_TARGET_X86ORX64
  17 #define JIT_F_CMOV              0x00000010
  18 #define JIT_F_SSE2              0x00000020
  19 #define JIT_F_SSE3              0x00000040
  20 #define JIT_F_SSE4_1            0x00000080
  21 #define JIT_F_P4                0x00000100
  22 #define JIT_F_PREFER_IMUL       0x00000200
  23 #define JIT_F_SPLIT_XMM         0x00000400
  24 #define JIT_F_LEA_AGU           0x00000800
  25
  26 /* Names for the CPU-specific flags. Must match the order above. */
  27 #define JIT_F_CPU_FIRST         JIT_F_CMOV
  28 #define JIT_F_CPUSTRING         "\4CMOV\4SSE2\4SSE3\6SSE4.1\2P4\3AMD\2K8\4ATOM"
  29 #else
  30 #error "Missing CPU-specific JIT engine flags"
  31 #endif
  32
  33 /* Optimization flags. */
  34 #define JIT_F_OPT_MASK          0x0fff0000
  35
  36 #define JIT_F_OPT_FOLD          0x00010000
  37 #define JIT_F_OPT_CSE           0x00020000
  38 #define JIT_F_OPT_DCE           0x00040000
  39 #define JIT_F_OPT_FWD           0x00080000
  40 #define JIT_F_OPT_DSE           0x00100000
  41 #define JIT_F_OPT_NARROW        0x00200000
  42 #define JIT_F_OPT_LOOP          0x00400000
  43 #define JIT_F_OPT_ABC           0x00800000
  44 #define JIT_F_OPT_FUSE          0x01000000
  45
  46 /* Optimizations names for -O. Must match the order above. */
  47 #define JIT_F_OPT_FIRST         JIT_F_OPT_FOLD
  48 #define JIT_F_OPTSTRING \
  49   "\4fold\3cse\3dce\3fwd\3dse\6narrow\4loop\3abc\4fuse"
  50
  51 /* Optimization levels set a fixed combination of flags. */
  52 #define JIT_F_OPT_0     0
  53 #define JIT_F_OPT_1     (JIT_F_OPT_FOLD|JIT_F_OPT_CSE|JIT_F_OPT_DCE)
  54 #define JIT_F_OPT_2     (JIT_F_OPT_1|JIT_F_OPT_NARROW|JIT_F_OPT_LOOP)
  55 #define JIT_F_OPT_3 \
  56   (JIT_F_OPT_2|JIT_F_OPT_FWD|JIT_F_OPT_DSE|JIT_F_OPT_ABC|JIT_F_OPT_FUSE)
  57 #define JIT_F_OPT_DEFAULT       JIT_F_OPT_3
  58
  59 #if LJ_TARGET_WINDOWS || LJ_64
  60 /* See: http://blogs.msdn.com/oldnewthing/archive/2003/10/08/55239.aspx */
  61 #define JIT_P_sizemcode_DEFAULT         64
  62 #else
  63 /* Could go as low as 4K, but the mmap() overhead would be rather high. */
  64 #define JIT_P_sizemcode_DEFAULT         32
  65 #endif
  66
  67 /* Optimization parameters and their defaults. Length is a char in octal! */
  68 #define JIT_PARAMDEF(_) \
  69   _(\010, maxtrace,     1000)   /* Max. # of traces in cache. */ \
  70   _(\011, maxrecord,    2000)   /* Max. # of recorded IR instructions. */ \
  71   _(\012, maxirconst,   500)    /* Max. # of IR constants of a trace. */ \
  72   _(\007, maxside,      100)    /* Max. # of side traces of a root trace. */ \
  73   _(\007, maxsnap,      100)    /* Max. # of snapshots for a trace. */ \
  74   \
  75   _(\007, hotloop,      56)     /* # of iter. to detect a hot loop/call. */ \
  76   _(\007, hotexit,      10)     /* # of taken exits to start a side trace. */ \
  77   _(\007, tryside,      4)      /* # of attempts to compile a side trace. */ \
  78   \
  79   _(\012, instunroll,   4)      /* Max. unroll for instable loops. */ \
  80   _(\012, loopunroll,   7)      /* Max. unroll for loop ops in side traces. */ \
  81   _(\012, callunroll,   3)      /* Max. unroll for recursive calls. */ \
  82   _(\011, recunroll,    2)      /* Min. unroll for true recursion. */ \
  83   \
  84   /* Size of each machine code area (in KBytes). */ \
  85   _(\011, sizemcode,    JIT_P_sizemcode_DEFAULT) \
  86   /* Max. total size of all machine code areas (in KBytes). */ \
  87   _(\010, maxmcode,     512) \
  88   /* End of list. */
  89
  90 enum {
  91 #define JIT_PARAMENUM(len, name, value) JIT_P_##name,
  92 JIT_PARAMDEF(JIT_PARAMENUM)
  93 #undef JIT_PARAMENUM
  94   JIT_P__MAX
  95 };
  96
  97 #define JIT_PARAMSTR(len, name, value)  #len #name
  98 #define JIT_P_STRING    JIT_PARAMDEF(JIT_PARAMSTR)
  99
 100 /* Trace compiler state. */
 101 typedef enum {
 102   LJ_TRACE_IDLE,        /* Trace compiler idle. */
 103   LJ_TRACE_ACTIVE = 0x10,
 104   LJ_TRACE_RECORD,      /* Bytecode recording active. */
 105   LJ_TRACE_START,       /* New trace started. */
 106   LJ_TRACE_END,         /* End of trace. */
 107   LJ_TRACE_ASM,         /* Assemble trace. */
 108   LJ_TRACE_ERR          /* Trace aborted with error. */
 109 } TraceState;
 110
 111 /* Post-processing action. */
 112 typedef enum {
 113   LJ_POST_NONE,         /* No action. */
 114   LJ_POST_FIXCOMP,      /* Fixup comparison and emit pending guard. */
 115   LJ_POST_FIXGUARD,     /* Fixup and emit pending guard. */
 116   LJ_POST_FIXBOOL,      /* Fixup boolean result. */
 117   LJ_POST_FFRETRY       /* Suppress recording of retried fast functions. */
 118 } PostProc;
 119
 120 /* Machine code type. */
 121 typedef uint8_t MCode;
 122
 123 /* Stack snapshot header. */
 124 typedef struct SnapShot {
 125   uint16_t mapofs;      /* Offset into snapshot map. */
 126   IRRef1 ref;           /* First IR ref for this snapshot. */
 127   uint8_t nslots;       /* Number of valid slots. */
 128   uint8_t nent;         /* Number of compressed entries. */
 129   uint8_t depth;        /* Number of frame links. */
 130   uint8_t count;        /* Count of taken exits for this snapshot. */
 131 } SnapShot;
 132
 133 #define SNAPCOUNT_DONE  255     /* Already compiled and linked a side trace. */
 134
 135 /* Compressed snapshot entry. */
 136 typedef uint32_t SnapEntry;
 137
 138 #define SNAP_FRAME              0x010000        /* Frame slot. */
 139 #define SNAP_CONT               0x020000        /* Continuation slot. */
 140 #define SNAP_NORESTORE          0x040000        /* No need to restore slot. */
 141 LJ_STATIC_ASSERT(SNAP_FRAME == TREF_FRAME);
 142 LJ_STATIC_ASSERT(SNAP_CONT == TREF_CONT);
 143
 144 #define SNAP(slot, flags, ref)  (((SnapEntry)(slot) << 24) + (flags) + (ref))
 145 #define SNAP_TR(slot, tr) \
 146   (((SnapEntry)(slot) << 24) + ((tr) & (TREF_CONT|TREF_FRAME|TREF_REFMASK)))
 147 #define SNAP_MKPC(pc)           ((SnapEntry)u32ptr(pc))
 148 #define SNAP_MKFTSZ(ftsz)       ((SnapEntry)(ftsz))
 149 #define snap_ref(sn)            ((sn) & 0xffff)
 150 #define snap_slot(sn)           ((BCReg)((sn) >> 24))
 151 #define snap_isframe(sn)        ((sn) & SNAP_FRAME)
 152 #define snap_pc(sn)             ((const BCIns *)(uintptr_t)(sn))
 153 #define snap_setref(sn, ref)    (((sn) & (0xffff0000&~SNAP_NORESTORE)) | (ref))
 154
 155 /* Snapshot and exit numbers. */
 156 typedef uint32_t SnapNo;
 157 typedef uint32_t ExitNo;
 158
 159 /* Trace number. */
 160 typedef uint32_t TraceNo;       /* Used to pass around trace numbers. */
 161 typedef uint16_t TraceNo1;      /* Stored trace number. */
 162
 163 #define TRACE_INTERP    0       /* Fallback to interpreter. */
 164
 165 /* Trace object. */
 166 typedef struct GCtrace {
 167   GCHeader;
 168   uint8_t topslot;      /* Top stack slot already checked to be allocated. */
 169   uint8_t unused1;
 170   IRRef nins;           /* Next IR instruction. Biased with REF_BIAS. */
 171   GCRef gclist;
 172   IRIns *ir;            /* IR instructions/constants. Biased with REF_BIAS. */
 173   IRRef nk;             /* Lowest IR constant. Biased with REF_BIAS. */
 174   uint16_t nsnap;       /* Number of snapshots. */
 175   uint16_t nsnapmap;    /* Number of snapshot map elements. */
 176   SnapShot *snap;       /* Snapshot array. */
 177   SnapEntry *snapmap;   /* Snapshot map. */
 178   GCRef startpt;        /* Starting prototype. */
 179   MRef startpc;         /* Bytecode PC of starting instruction. */
 180   BCIns startins;       /* Original bytecode of starting instruction. */
 181   MSize szmcode;        /* Size of machine code. */
 182   MCode *mcode;         /* Start of machine code. */
 183   MSize mcloop;         /* Offset of loop start in machine code. */
 184   uint16_t nchild;      /* Number of child traces (root trace only). */
 185   uint16_t spadjust;    /* Stack pointer adjustment (offset in bytes). */
 186   TraceNo1 traceno;     /* Trace number. */
 187   TraceNo1 link;        /* Linked trace (or self for loops). */
 188   TraceNo1 root;        /* Root trace of side trace (or 0 for root traces). */
 189   TraceNo1 nextroot;    /* Next root trace for same prototype. */
 190   TraceNo1 nextside;    /* Next side trace of same root trace. */
 191   uint16_t unused2;
 192 #ifdef LUAJIT_USE_GDBJIT
 193   void *gdbjit_entry;   /* GDB JIT entry. */
 194 #endif
 195 } GCtrace;
 196
 197 #define gco2trace(o)    check_exp((o)->gch.gct == ~LJ_TTRACE, (GCtrace *)(o))
 198 #define traceref(J, n) \
 199   check_exp((n)>0 && (MSize)(n)<J->sizetrace, (GCtrace *)gcref(J->trace[(n)]))
 200
 201 LJ_STATIC_ASSERT(offsetof(GChead, gclist) == offsetof(GCtrace, gclist));
 202
 203 /* Round-robin penalty cache for bytecodes leading to aborted traces. */
 204 typedef struct HotPenalty {
 205   MRef pc;              /* Starting bytecode PC. */
 206   uint16_t val;         /* Penalty value, i.e. hotcount start. */
 207   uint16_t reason;      /* Abort reason (really TraceErr). */
 208 } HotPenalty;
 209
 210 #define PENALTY_SLOTS   64      /* Penalty cache slot. Must be a power of 2. */
 211 #define PENALTY_MIN     36      /* Minimum penalty value. */
 212 #define PENALTY_MAX     60000   /* Maximum penalty value. */
 213 #define PENALTY_RNDBITS 4       /* # of random bits to add to penalty value. */
 214
 215 /* Round-robin backpropagation cache for narrowing conversions. */
 216 typedef struct BPropEntry {
 217   IRRef1 key;           /* Key: original reference. */
 218   IRRef1 val;           /* Value: reference after conversion. */
 219   IRRef mode;           /* Mode for this entry (currently IRCONV_*). */
 220 } BPropEntry;
 221
 222 /* Number of slots for the backpropagation cache. Must be a power of 2. */
 223 #define BPROP_SLOTS     16
 224
 225 /* Scalar evolution analysis cache. */
 226 typedef struct ScEvEntry {
 227   IRRef1 idx;           /* Index reference. */
 228   IRRef1 start;         /* Constant start reference. */
 229   IRRef1 stop;          /* Constant stop reference. */
 230   IRRef1 step;          /* Constant step reference. */
 231   IRType1 t;            /* Scalar type. */
 232   uint8_t dir;          /* Direction. 1: +, 0: -. */
 233 } ScEvEntry;
 234
 235 /* 128 bit SIMD constants. */
 236 enum {
 237   LJ_KSIMD_ABS,
 238   LJ_KSIMD_NEG,
 239   LJ_KSIMD__MAX
 240 };
 241
 242 /* Get 16 byte aligned pointer to SIMD constant. */
 243 #define LJ_KSIMD(J, n) \
 244   ((TValue *)(((intptr_t)&J->ksimd[2*(n)] + 15) & ~(intptr_t)15))
 245
 246 /* Set/reset flag to activate the SPLIT pass for the current trace. */
 247 #if LJ_32 && LJ_HASFFI
 248 #define lj_needsplit(J)         (J->needsplit = 1)
 249 #define lj_resetsplit(J)        (J->needsplit = 0)
 250 #else
 251 #define lj_needsplit(J)         UNUSED(J)
 252 #define lj_resetsplit(J)        UNUSED(J)
 253 #endif
 254
 255 /* Fold state is used to fold instructions on-the-fly. */
 256 typedef struct FoldState {
 257   IRIns ins;            /* Currently emitted instruction. */
 258   IRIns left;           /* Instruction referenced by left operand. */
 259   IRIns right;          /* Instruction referenced by right operand. */
 260 } FoldState;
 261
 262 /* JIT compiler state. */
 263 typedef struct jit_State {
 264   GCtrace cur;          /* Current trace. */
 265
 266   lua_State *L;         /* Current Lua state. */
 267   const BCIns *pc;      /* Current PC. */
 268   GCfunc *fn;           /* Current function. */
 269   GCproto *pt;          /* Current prototype. */
 270   TRef *base;           /* Current frame base, points into J->slots. */
 271
 272   uint32_t flags;       /* JIT engine flags. */
 273   BCReg maxslot;        /* Relative to baseslot. */
 274   BCReg baseslot;       /* Current frame base, offset into J->slots. */
 275
 276   uint8_t mergesnap;    /* Allowed to merge with next snapshot. */
 277   uint8_t needsnap;     /* Need snapshot before recording next bytecode. */
 278   IRType1 guardemit;    /* Accumulated IRT_GUARD for emitted instructions. */
 279   uint8_t bcskip;       /* Number of bytecode instructions to skip. */
 280
 281   FoldState fold;       /* Fold state. */
 282
 283   const BCIns *bc_min;  /* Start of allowed bytecode range for root trace. */
 284   MSize bc_extent;      /* Extent of the range. */
 285
 286   TraceState state;     /* Trace compiler state. */
 287
 288   int32_t instunroll;   /* Unroll counter for instable loops. */
 289   int32_t loopunroll;   /* Unroll counter for loop ops in side traces. */
 290   int32_t tailcalled;   /* Number of successive tailcalls. */
 291   int32_t framedepth;   /* Current frame depth. */
 292   int32_t retdepth;     /* Return frame depth (count of RETF). */
 293
 294   MRef k64;             /* Pointer to chained array of 64 bit constants. */
 295   TValue ksimd[LJ_KSIMD__MAX*2+1];  /* 16 byte aligned SIMD constants. */
 296
 297   IRIns *irbuf;         /* Temp. IR instruction buffer. Biased with REF_BIAS. */
 298   IRRef irtoplim;       /* Upper limit of instuction buffer (biased). */
 299   IRRef irbotlim;       /* Lower limit of instuction buffer (biased). */
 300   IRRef loopref;        /* Last loop reference or ref of final LOOP (or 0). */
 301
 302   MSize sizesnap;       /* Size of temp. snapshot buffer. */
 303   SnapShot *snapbuf;    /* Temp. snapshot buffer. */
 304   SnapEntry *snapmapbuf;  /* Temp. snapshot map buffer. */
 305   MSize sizesnapmap;    /* Size of temp. snapshot map buffer. */
 306
 307   PostProc postproc;    /* Required post-processing after execution. */
 308 #if LJ_32 && LJ_HASFFI
 309   int needsplit;        /* Need SPLIT pass. */
 310 #endif
 311
 312   GCRef *trace;         /* Array of traces. */
 313   TraceNo freetrace;    /* Start of scan for next free trace. */
 314   MSize sizetrace;      /* Size of trace array. */
 315
 316   IRRef1 chain[IR__MAX];  /* IR instruction skip-list chain anchors. */
 317   TRef slot[LJ_MAX_JSLOTS+LJ_STACK_EXTRA];  /* Stack slot map. */
 318
 319   int32_t param[JIT_P__MAX];  /* JIT engine parameters. */
 320
 321   MCode *exitstubgroup[LJ_MAX_EXITSTUBGR];  /* Exit stub group addresses. */
 322
 323   HotPenalty penalty[PENALTY_SLOTS];  /* Penalty slots. */
 324   uint32_t penaltyslot; /* Round-robin index into penalty slots. */
 325   uint32_t prngstate;   /* PRNG state. */
 326
 327   BPropEntry bpropcache[BPROP_SLOTS];  /* Backpropagation cache slots. */
 328   uint32_t bpropslot;   /* Round-robin index into bpropcache slots. */
 329
 330   ScEvEntry scev;       /* Scalar evolution analysis cache slots. */
 331
 332   const BCIns *startpc; /* Bytecode PC of starting instruction. */
 333   TraceNo parent;       /* Parent of current side trace (0 for root traces). */
 334   ExitNo exitno;        /* Exit number in parent of current side trace. */
 335
 336   BCIns *patchpc;       /* PC for pending re-patch. */
 337   BCIns patchins;       /* Instruction for pending re-patch. */
 338
 339   int mcprot;           /* Protection of current mcode area. */
 340   MCode *mcarea;        /* Base of current mcode area. */
 341   MCode *mctop;         /* Top of current mcode area. */
 342   MCode *mcbot;         /* Bottom of current mcode area. */
 343   size_t szmcarea;      /* Size of current mcode area. */
 344   size_t szallmcarea;   /* Total size of all allocated mcode areas. */
 345
 346   TValue errinfo;       /* Additional info element for trace errors. */
 347 } jit_State;
 348
 349 /* Trivial PRNG e.g. used for penalty randomization. */
 350 static LJ_AINLINE uint32_t LJ_PRNG_BITS(jit_State *J, int bits)
 351 {
 352   /* Yes, this LCG is very weak, but that doesn't matter for our use case. */
 353   J->prngstate = J->prngstate * 1103515245 + 12345;
 354   return J->prngstate >> (32-bits);
 355 }
 356
 357 /* Exit stubs. */
 358 #if LJ_TARGET_X86ORX64
 359 /* Limited by the range of a short fwd jump (127): (2+2)*(32-1)-2 = 122. */
 360 #define EXITSTUB_SPACING        (2+2)
 361 #define EXITSTUBS_PER_GROUP     32
 362 #else
 363 #error "Missing CPU-specific exit stub definitions"
 364 #endif
 365
 366 /* Return the address of an exit stub. */
 367 static LJ_AINLINE MCode *exitstub_addr(jit_State *J, ExitNo exitno)
 368 {
 369   lua_assert(J->exitstubgroup[exitno / EXITSTUBS_PER_GROUP] != NULL);
 370   return J->exitstubgroup[exitno / EXITSTUBS_PER_GROUP] +
 371          EXITSTUB_SPACING*(exitno % EXITSTUBS_PER_GROUP);
 372 }
 373
 374 #endif