One Level Up Top Level

src/lj_opt_narrow.c - luajit-2.0-src

Data types defined

Functions defined

Macros defined

Source code

  1. /*
  2. ** NARROW: Narrowing of numbers to integers (double to int32_t).
  3. ** STRIPOV: Stripping of overflow checks.
  4. ** Copyright (C) 2005-2015 Mike Pall. See Copyright Notice in luajit.h
  5. */

  7. ‌#define lj_opt_narrow_c
  8. ‌#define LUA_CORE

  10. #include "lj_obj.h"

  12. #if LJ_HASJIT

  14. #include "lj_bc.h"
  15. #include "lj_ir.h"
  16. #include "lj_jit.h"
  17. #include "lj_iropt.h"
  18. #include "lj_trace.h"
  19. #include "lj_vm.h"
  20. #include "lj_strscan.h"

  22. /* Rationale for narrowing optimizations:
  23. **
  24. ** Lua has only a single number type and this is a FP double by default.
  25. ** Narrowing doubles to integers does not pay off for the interpreter on a
  26. ** current-generation x86/x64 machine. Most FP operations need the same
  27. ** amount of execution resources as their integer counterparts, except
  28. ** with slightly longer latencies. Longer latencies are a non-issue for
  29. ** the interpreter, since they are usually hidden by other overhead.
  30. **
  31. ** The total CPU execution bandwidth is the sum of the bandwidth of the FP
  32. ** and the integer units, because they execute in parallel. The FP units
  33. ** have an equal or higher bandwidth than the integer units. Not using
  34. ** them means losing execution bandwidth. Moving work away from them to
  35. ** the already quite busy integer units is a losing proposition.
  36. **
  37. ** The situation for JIT-compiled code is a bit different: the higher code
  38. ** density makes the extra latencies much more visible. Tight loops expose
  39. ** the latencies for updating the induction variables. Array indexing
  40. ** requires narrowing conversions with high latencies and additional
  41. ** guards (to check that the index is really an integer). And many common
  42. ** optimizations only work on integers.
  43. **
  44. ** One solution would be speculative, eager narrowing of all number loads.
  45. ** This causes many problems, like losing -0 or the need to resolve type
  46. ** mismatches between traces. It also effectively forces the integer type
  47. ** to have overflow-checking semantics. This impedes many basic
  48. ** optimizations and requires adding overflow checks to all integer
  49. ** arithmetic operations (whereas FP arithmetics can do without).
  50. **
  51. ** Always replacing an FP op with an integer op plus an overflow check is
  52. ** counter-productive on a current-generation super-scalar CPU. Although
  53. ** the overflow check branches are highly predictable, they will clog the
  54. ** execution port for the branch unit and tie up reorder buffers. This is
  55. ** turning a pure data-flow dependency into a different data-flow
  56. ** dependency (with slightly lower latency) *plus* a control dependency.
  57. ** In general, you don't want to do this since latencies due to data-flow
  58. ** dependencies can be well hidden by out-of-order execution.
  59. **
  60. ** A better solution is to keep all numbers as FP values and only narrow
  61. ** when it's beneficial to do so. LuaJIT uses predictive narrowing for
  62. ** induction variables and demand-driven narrowing for index expressions,
  63. ** integer arguments and bit operations. Additionally it can eliminate or
  64. ** hoist most of the resulting overflow checks. Regular arithmetic
  65. ** computations are never narrowed to integers.
  66. **
  67. ** The integer type in the IR has convenient wrap-around semantics and
  68. ** ignores overflow. Extra operations have been added for
  69. ** overflow-checking arithmetic (ADDOV/SUBOV) instead of an extra type.
  70. ** Apart from reducing overall complexity of the compiler, this also
  71. ** nicely solves the problem where you want to apply algebraic
  72. ** simplifications to ADD, but not to ADDOV. And the x86/x64 assembler can
  73. ** use lea instead of an add for integer ADD, but not for ADDOV (lea does
  74. ** not affect the flags, but it helps to avoid register moves).
  75. **
  76. **
  77. ** All of the above has to be reconsidered for architectures with slow FP
  78. ** operations or without a hardware FPU. The dual-number mode of LuaJIT
  79. ** addresses this issue. Arithmetic operations are performed on integers
  80. ** as far as possible and overflow checks are added as needed.
  81. **
  82. ** This implies that narrowing for integer arguments and bit operations
  83. ** should also strip overflow checks, e.g. replace ADDOV with ADD. The
  84. ** original overflow guards are weak and can be eliminated by DCE, if
  85. ** there's no other use.
  86. **
  87. ** A slight twist is that it's usually beneficial to use overflow-checked
  88. ** integer arithmetics if all inputs are already integers. This is the only
  89. ** change that affects the single-number mode, too.
  90. */

  92. /* Some local macros to save typing. Undef'd at the end. */
  93. ‌#define IR(ref)                        (&J->cur.ir[(ref)])
  94. ‌#define fins                        (&J->fold.ins)

  96. /* Pass IR on to next optimization in chain (FOLD). */
  97. ‌#define emitir(ot, a, b)        (lj_ir_set(J, (ot), (a), (b)), lj_opt_fold(J))

  99. ‌#define emitir_raw(ot, a, b)        (lj_ir_set(J, (ot), (a), (b)), lj_ir_emit(J))

  101. /* -- Elimination of narrowing type conversions --------------------------- */

  103. /* Narrowing of index expressions and bit operations is demand-driven. The
  104. ** trace recorder emits a narrowing type conversion (CONV.int.num or TOBIT)
  105. ** in all of these cases (e.g. array indexing or string indexing). FOLD
  106. ** already takes care of eliminating simple redundant conversions like
  107. ** CONV.int.num(CONV.num.int(x)) ==> x.
  108. **
  109. ** But the surrounding code is FP-heavy and arithmetic operations are
  110. ** performed on FP numbers (for the single-number mode). Consider a common
  111. ** example such as 'x=t[i+1]', with 'i' already an integer (due to induction
  112. ** variable narrowing). The index expression would be recorded as
  113. **   CONV.int.num(ADD(CONV.num.int(i), 1))
  114. ** which is clearly suboptimal.
  115. **
  116. ** One can do better by recursively backpropagating the narrowing type
  117. ** conversion across FP arithmetic operations. This turns FP ops into
  118. ** their corresponding integer counterparts. Depending on the semantics of
  119. ** the conversion they also need to check for overflow. Currently only ADD
  120. ** and SUB are supported.
  121. **
  122. ** The above example can be rewritten as
  123. **   ADDOV(CONV.int.num(CONV.num.int(i)), 1)
  124. ** and then into ADDOV(i, 1) after folding of the conversions. The original
  125. ** FP ops remain in the IR and are eliminated by DCE since all references to
  126. ** them are gone.
  127. **
  128. ** [In dual-number mode the trace recorder already emits ADDOV etc., but
  129. ** this can be further reduced. See below.]
  130. **
  131. ** Special care has to be taken to avoid narrowing across an operation
  132. ** which is potentially operating on non-integral operands. One obvious
  133. ** case is when an expression contains a non-integral constant, but ends
  134. ** up as an integer index at runtime (like t[x+1.5] with x=0.5).
  135. **
  136. ** Operations with two non-constant operands illustrate a similar problem
  137. ** (like t[a+b] with a=1.5 and b=2.5). Backpropagation has to stop there,
  138. ** unless it can be proven that either operand is integral (e.g. by CSEing
  139. ** a previous conversion). As a not-so-obvious corollary this logic also
  140. ** applies for a whole expression tree (e.g. t[(a+1)+(b+1)]).
  141. **
  142. ** Correctness of the transformation is guaranteed by avoiding to expand
  143. ** the tree by adding more conversions than the one we would need to emit
  144. ** if not backpropagating. TOBIT employs a more optimistic rule, because
  145. ** the conversion has special semantics, designed to make the life of the
  146. ** compiler writer easier. ;-)
  147. **
  148. ** Using on-the-fly backpropagation of an expression tree doesn't work
  149. ** because it's unknown whether the transform is correct until the end.
  150. ** This either requires IR rollback and cache invalidation for every
  151. ** subtree or a two-pass algorithm. The former didn't work out too well,
  152. ** so the code now combines a recursive collector with a stack-based
  153. ** emitter.
  154. **
  155. ** [A recursive backpropagation algorithm with backtracking, employing
  156. ** skip-list lookup and round-robin caching, emitting stack operations
  157. ** on-the-fly for a stack-based interpreter -- and all of that in a meager
  158. ** kilobyte? Yep, compilers are a great treasure chest. Throw away your
  159. ** textbooks and read the codebase of a compiler today!]
  160. **
  161. ** There's another optimization opportunity for array indexing: it's
  162. ** always accompanied by an array bounds-check. The outermost overflow
  163. ** check may be delegated to the ABC operation. This works because ABC is
  164. ** an unsigned comparison and wrap-around due to overflow creates negative
  165. ** numbers.
  166. **
  167. ** But this optimization is only valid for constants that cannot overflow
  168. ** an int32_t into the range of valid array indexes [0..2^27+1). A check
  169. ** for +-2^30 is safe since -2^31 - 2^30 wraps to 2^30 and 2^31-1 + 2^30
  170. ** wraps to -2^30-1.
  171. **
  172. ** It's also good enough in practice, since e.g. t[i+1] or t[i-10] are
  173. ** quite common. So the above example finally ends up as ADD(i, 1)!
  174. **
  175. ** Later on, the assembler is able to fuse the whole array reference and
  176. ** the ADD into the memory operands of loads and other instructions. This
  177. ** is why LuaJIT is able to generate very pretty (and fast) machine code
  178. ** for array indexing. And that, my dear, concludes another story about
  179. ** one of the hidden secrets of LuaJIT ...
  180. */

  182. /* Maximum backpropagation depth and maximum stack size. */
  183. ‌#define NARROW_MAX_BACKPROP        100
  184. ‌#define NARROW_MAX_STACK        256

  186. /* The stack machine has a 32 bit instruction format: [IROpT | IRRef1]
  187. ** The lower 16 bits hold a reference (or 0). The upper 16 bits hold
  188. ** the IR opcode + type or one of the following special opcodes:
  189. */
  190. enum {
  191.   NARROW_REF,                /* Push ref. */
  192.   NARROW_CONV,                /* Push conversion of ref. */
  193.   NARROW_SEXT,                /* Push sign-extension of ref. */
  194.   NARROW_INT                /* Push KINT ref. The next code holds an int32_t. */
  195. };

  197. ‌typedef uint32_t NarrowIns;

  199. ‌#define NARROWINS(op, ref)        (((op) << 16) + (ref))
  200. ‌#define narrow_op(ins)                ((IROpT)((ins) >> 16))
  201. ‌#define narrow_ref(ins)                ((IRRef1)(ins))

  203. /* Context used for narrowing of type conversions. */
  204. ‌typedef struct NarrowConv {
  205.   jit_State *J;                /* JIT compiler state. */
  206.   NarrowIns *sp;        /* Current stack pointer. */
  207.   NarrowIns *maxsp;        /* Maximum stack pointer minus redzone. */
  208.   int lim;                /* Limit on the number of emitted conversions. */
  209.   IRRef mode;                /* Conversion mode (IRCONV_*). */
  210.   IRType t;                /* Destination type: IRT_INT or IRT_I64. */
  211.   NarrowIns stack[NARROW_MAX_STACK];  /* Stack holding stack-machine code. */
  212. ‌} NarrowConv;

  214. /* Lookup a reference in the backpropagation cache. */
  215. ‌static BPropEntry *narrow_bpc_get(jit_State *J, IRRef1 key, IRRef mode)
  216. {
  217.   ptrdiff_t i;
  218.   for (i = 0; i < BPROP_SLOTS; i++) {
  219.     BPropEntry *bp = &J->bpropcache[i];
  220.     /* Stronger checks are ok, too. */
  221.     if (bp->key == key && bp->mode >= mode &&
  222.         ((bp->mode ^ mode) & IRCONV_MODEMASK) == 0)
  223.       return bp;
  224.   }
  225.   return NULL;
  226. }

  228. /* Add an entry to the backpropagation cache. */
  229. ‌static void narrow_bpc_set(jit_State *J, IRRef1 key, IRRef1 val, IRRef mode)
  230. {
  231.   uint32_t slot = J->bpropslot;
  232.   BPropEntry *bp = &J->bpropcache[slot];
  233.   J->bpropslot = (slot + 1) & (BPROP_SLOTS-1);
  234.   bp->key = key;
  235.   bp->val = val;
  236.   bp->mode = mode;
  237. }

  239. /* Backpropagate overflow stripping. */
  240. ‌static void narrow_stripov_backprop(NarrowConv *nc, IRRef ref, int depth)
  241. {
  242.   jit_State *J = nc->J;
  243.   IRIns *ir = IR(ref);
  244.   if (ir->o == IR_ADDOV || ir->o == IR_SUBOV ||
  245.       (ir->o == IR_MULOV && (nc->mode & IRCONV_CONVMASK) == IRCONV_ANY)) {
  246.     BPropEntry *bp = narrow_bpc_get(nc->J, ref, IRCONV_TOBIT);
  247.     if (bp) {
  248.       ref = bp->val;
  249.     } else if (++depth < NARROW_MAX_BACKPROP && nc->sp < nc->maxsp) {
  250.       narrow_stripov_backprop(nc, ir->op1, depth);
  251.       narrow_stripov_backprop(nc, ir->op2, depth);
  252.       *nc->sp++ = NARROWINS(IRT(ir->o - IR_ADDOV + IR_ADD, IRT_INT), ref);
  253.       return;
  254.     }
  255.   }
  256.   *nc->sp++ = NARROWINS(NARROW_REF, ref);
  257. }

  259. /* Backpropagate narrowing conversion. Return number of needed conversions. */
  260. ‌static int narrow_conv_backprop(NarrowConv *nc, IRRef ref, int depth)
  261. {
  262.   jit_State *J = nc->J;
  263.   IRIns *ir = IR(ref);
  264.   IRRef cref;

  266.   /* Check the easy cases first. */
  267.   if (ir->o == IR_CONV && (ir->op2 & IRCONV_SRCMASK) == IRT_INT) {
  268.     if ((nc->mode & IRCONV_CONVMASK) <= IRCONV_ANY)
  269.       narrow_stripov_backprop(nc, ir->op1, depth+1);
  270.     else
  271.       *nc->sp++ = NARROWINS(NARROW_REF, ir->op1);  /* Undo conversion. */
  272.     if (nc->t == IRT_I64)
  273.       *nc->sp++ = NARROWINS(NARROW_SEXT, 0);  /* Sign-extend integer. */
  274.     return 0;
  275.   } else if (ir->o == IR_KNUM) {  /* Narrow FP constant. */
  276.     lua_Number n = ir_knum(ir)->n;
  277.     if ((nc->mode & IRCONV_CONVMASK) == IRCONV_TOBIT) {
  278.       /* Allows a wider range of constants. */
  279.       int64_t k64 = (int64_t)n;
  280.       if (n == (lua_Number)k64) {  /* Only if const doesn't lose precision. */
  281.         *nc->sp++ = NARROWINS(NARROW_INT, 0);
  282.         *nc->sp++ = (NarrowIns)k64;  /* But always truncate to 32 bits. */
  283.         return 0;
  284.       }
  285.     } else {
  286.       int32_t k = lj_num2int(n);
  287.       /* Only if constant is a small integer. */
  288.       if (checki16(k) && n == (lua_Number)k) {
  289.         *nc->sp++ = NARROWINS(NARROW_INT, 0);
  290.         *nc->sp++ = (NarrowIns)k;
  291.         return 0;
  292.       }
  293.     }
  294.     return 10;  /* Never narrow other FP constants (this is rare). */
  295.   }

  297.   /* Try to CSE the conversion. Stronger checks are ok, too. */
  298.   cref = J->chain[fins->o];
  299.   while (cref > ref) {
  300.     IRIns *cr = IR(cref);
  301.     if (cr->op1 == ref &&
  302.         (fins->o == IR_TOBIT ||
  303.          ((cr->op2 & IRCONV_MODEMASK) == (nc->mode & IRCONV_MODEMASK) &&
  304.           irt_isguard(cr->t) >= irt_isguard(fins->t)))) {
  305.       *nc->sp++ = NARROWINS(NARROW_REF, cref);
  306.       return 0;  /* Already there, no additional conversion needed. */
  307.     }
  308.     cref = cr->prev;
  309.   }

  311.   /* Backpropagate across ADD/SUB. */
  312.   if (ir->o == IR_ADD || ir->o == IR_SUB) {
  313.     /* Try cache lookup first. */
  314.     IRRef mode = nc->mode;
  315.     BPropEntry *bp;
  316.     /* Inner conversions need a stronger check. */
  317.     if ((mode & IRCONV_CONVMASK) == IRCONV_INDEX && depth > 0)
  318.       mode += IRCONV_CHECK-IRCONV_INDEX;
  319.     bp = narrow_bpc_get(nc->J, (IRRef1)ref, mode);
  320.     if (bp) {
  321.       *nc->sp++ = NARROWINS(NARROW_REF, bp->val);
  322.       return 0;
  323.     } else if (nc->t == IRT_I64) {
  324.       /* Try sign-extending from an existing (checked) conversion to int. */
  325.       mode = (IRT_INT<<5)|IRT_NUM|IRCONV_INDEX;
  326.       bp = narrow_bpc_get(nc->J, (IRRef1)ref, mode);
  327.       if (bp) {
  328.         *nc->sp++ = NARROWINS(NARROW_REF, bp->val);
  329.         *nc->sp++ = NARROWINS(NARROW_SEXT, 0);
  330.         return 0;
  331.       }
  332.     }
  333.     if (++depth < NARROW_MAX_BACKPROP && nc->sp < nc->maxsp) {
  334.       NarrowIns *savesp = nc->sp;
  335.       int count = narrow_conv_backprop(nc, ir->op1, depth);
  336.       count += narrow_conv_backprop(nc, ir->op2, depth);
  337.       if (count <= nc->lim) {  /* Limit total number of conversions. */
  338.         *nc->sp++ = NARROWINS(IRT(ir->o, nc->t), ref);
  339.         return count;
  340.       }
  341.       nc->sp = savesp;  /* Too many conversions, need to backtrack. */
  342.     }
  343.   }

  345.   /* Otherwise add a conversion. */
  346.   *nc->sp++ = NARROWINS(NARROW_CONV, ref);
  347.   return 1;
  348. }

  350. /* Emit the conversions collected during backpropagation. */
  351. ‌static IRRef narrow_conv_emit(jit_State *J, NarrowConv *nc)
  352. {
  353.   /* The fins fields must be saved now -- emitir() overwrites them. */
  354.   IROpT guardot = irt_isguard(fins->t) ? IRTG(IR_ADDOV-IR_ADD, 0) : 0;
  355.   IROpT convot = fins->ot;
  356.   IRRef1 convop2 = fins->op2;
  357.   NarrowIns *next = nc->stack;  /* List of instructions from backpropagation. */
  358.   NarrowIns *last = nc->sp;
  359.   NarrowIns *sp = nc->stack;  /* Recycle the stack to store operands. */
  360.   while (next < last) {  /* Simple stack machine to process the ins. list. */
  361.     NarrowIns ref = *next++;
  362.     IROpT op = narrow_op(ref);
  363.     if (op == NARROW_REF) {
  364.       *sp++ = ref;
  365.     } else if (op == NARROW_CONV) {
  366.       *sp++ = emitir_raw(convot, ref, convop2);  /* Raw emit avoids a loop. */
  367.     } else if (op == NARROW_SEXT) {
  368.       lua_assert(sp >= nc->stack+1);
  369.       sp[-1] = emitir(IRT(IR_CONV, IRT_I64), sp[-1],
  370.                       (IRT_I64<<5)|IRT_INT|IRCONV_SEXT);
  371.     } else if (op == NARROW_INT) {
  372.       lua_assert(next < last);
  373.       *sp++ = nc->t == IRT_I64 ?
  374.               lj_ir_kint64(J, (int64_t)(int32_t)*next++) :
  375.               lj_ir_kint(J, *next++);
  376.     } else {  /* Regular IROpT. Pops two operands and pushes one result. */
  377.       IRRef mode = nc->mode;
  378.       lua_assert(sp >= nc->stack+2);
  379.       sp--;
  380.       /* Omit some overflow checks for array indexing. See comments above. */
  381.       if ((mode & IRCONV_CONVMASK) == IRCONV_INDEX) {
  382.         if (next == last && irref_isk(narrow_ref(sp[0])) &&
  383.           (uint32_t)IR(narrow_ref(sp[0]))->i + 0x40000000u < 0x80000000u)
  384.           guardot = 0;
  385.         else  /* Otherwise cache a stronger check. */
  386.           mode += IRCONV_CHECK-IRCONV_INDEX;
  387.       }
  388.       sp[-1] = emitir(op+guardot, sp[-1], sp[0]);
  389.       /* Add to cache. */
  390.       if (narrow_ref(ref))
  391.         narrow_bpc_set(J, narrow_ref(ref), narrow_ref(sp[-1]), mode);
  392.     }
  393.   }
  394.   lua_assert(sp == nc->stack+1);
  395.   return nc->stack[0];
  396. }

  398. /* Narrow a type conversion of an arithmetic operation. */
  399. ‌TRef LJ_FASTCALL lj_opt_narrow_convert(jit_State *J)
  400. {
  401.   if ((J->flags & JIT_F_OPT_NARROW)) {
  402.     NarrowConv nc;
  403.     nc.J = J;
  404.     nc.sp = nc.stack;
  405.     nc.maxsp = &nc.stack[NARROW_MAX_STACK-4];
  406.     nc.t = irt_type(fins->t);
  407.     if (fins->o == IR_TOBIT) {
  408.       nc.mode = IRCONV_TOBIT;  /* Used only in the backpropagation cache. */
  409.       nc.lim = 2;  /* TOBIT can use a more optimistic rule. */
  410.     } else {
  411.       nc.mode = fins->op2;
  412.       nc.lim = 1;
  413.     }
  414.     if (narrow_conv_backprop(&nc, fins->op1, 0) <= nc.lim)
  415.       return narrow_conv_emit(J, &nc);
  416.   }
  417.   return NEXTFOLD;
  418. }

  420. /* -- Narrowing of implicit conversions ----------------------------------- */

  422. /* Recursively strip overflow checks. */
  423. ‌static TRef narrow_stripov(jit_State *J, TRef tr, int lastop, IRRef mode)
  424. {
  425.   IRRef ref = tref_ref(tr);
  426.   IRIns *ir = IR(ref);
  427.   int op = ir->o;
  428.   if (op >= IR_ADDOV && op <= lastop) {
  429.     BPropEntry *bp = narrow_bpc_get(J, ref, mode);
  430.     if (bp) {
  431.       return TREF(bp->val, irt_t(IR(bp->val)->t));
  432.     } else {
  433.       IRRef op1 = ir->op1, op2 = ir->op2;  /* The IR may be reallocated. */
  434.       op1 = narrow_stripov(J, op1, lastop, mode);
  435.       op2 = narrow_stripov(J, op2, lastop, mode);
  436.       tr = emitir(IRT(op - IR_ADDOV + IR_ADD,
  437.                       ((mode & IRCONV_DSTMASK) >> IRCONV_DSH)), op1, op2);
  438.       narrow_bpc_set(J, ref, tref_ref(tr), mode);
  439.     }
  440.   } else if (LJ_64 && (mode & IRCONV_SEXT) && !irt_is64(ir->t)) {
  441.     tr = emitir(IRT(IR_CONV, IRT_INTP), tr, mode);
  442.   }
  443.   return tr;
  444. }

  446. /* Narrow array index. */
  447. ‌TRef LJ_FASTCALL lj_opt_narrow_index(jit_State *J, TRef tr)
  448. {
  449.   IRIns *ir;
  450.   lua_assert(tref_isnumber(tr));
  451.   if (tref_isnum(tr))  /* Conversion may be narrowed, too. See above. */
  452.     return emitir(IRTGI(IR_CONV), tr, IRCONV_INT_NUM|IRCONV_INDEX);
  453.   /* Omit some overflow checks for array indexing. See comments above. */
  454.   ir = IR(tref_ref(tr));
  455.   if ((ir->o == IR_ADDOV || ir->o == IR_SUBOV) && irref_isk(ir->op2) &&
  456.       (uint32_t)IR(ir->op2)->i + 0x40000000u < 0x80000000u)
  457.     return emitir(IRTI(ir->o - IR_ADDOV + IR_ADD), ir->op1, ir->op2);
  458.   return tr;
  459. }

  461. /* Narrow conversion to integer operand (overflow undefined). */
  462. ‌TRef LJ_FASTCALL lj_opt_narrow_toint(jit_State *J, TRef tr)
  463. {
  464.   if (tref_isstr(tr))
  465.     tr = emitir(IRTG(IR_STRTO, IRT_NUM), tr, 0);
  466.   if (tref_isnum(tr))  /* Conversion may be narrowed, too. See above. */
  467.     return emitir(IRTI(IR_CONV), tr, IRCONV_INT_NUM|IRCONV_ANY);
  468.   if (!tref_isinteger(tr))
  469.     lj_trace_err(J, LJ_TRERR_BADTYPE);
  470.   /*
  471.   ** Undefined overflow semantics allow stripping of ADDOV, SUBOV and MULOV.
  472.   ** Use IRCONV_TOBIT for the cache entries, since the semantics are the same.
  473.   */
  474.   return narrow_stripov(J, tr, IR_MULOV, (IRT_INT<<5)|IRT_INT|IRCONV_TOBIT);
  475. }

  477. /* Narrow conversion to bitop operand (overflow wrapped). */
  478. ‌TRef LJ_FASTCALL lj_opt_narrow_tobit(jit_State *J, TRef tr)
  479. {
  480.   if (tref_isstr(tr))
  481.     tr = emitir(IRTG(IR_STRTO, IRT_NUM), tr, 0);
  482.   if (tref_isnum(tr))  /* Conversion may be narrowed, too. See above. */
  483.     return emitir(IRTI(IR_TOBIT), tr, lj_ir_knum_tobit(J));
  484.   if (!tref_isinteger(tr))
  485.     lj_trace_err(J, LJ_TRERR_BADTYPE);
  486.   /*
  487.   ** Wrapped overflow semantics allow stripping of ADDOV and SUBOV.
  488.   ** MULOV cannot be stripped due to precision widening.
  489.   */
  490.   return narrow_stripov(J, tr, IR_SUBOV, (IRT_INT<<5)|IRT_INT|IRCONV_TOBIT);
  491. }

  493. #if LJ_HASFFI
  494. /* Narrow C array index (overflow undefined). */
  495. ‌TRef LJ_FASTCALL lj_opt_narrow_cindex(jit_State *J, TRef tr)
  496. {
  497.   lua_assert(tref_isnumber(tr));
  498.   if (tref_isnum(tr))
  499.     return emitir(IRT(IR_CONV, IRT_INTP), tr, (IRT_INTP<<5)|IRT_NUM|IRCONV_ANY);
  500.   /* Undefined overflow semantics allow stripping of ADDOV, SUBOV and MULOV. */
  501.   return narrow_stripov(J, tr, IR_MULOV,
  502.                         LJ_64 ? ((IRT_INTP<<5)|IRT_INT|IRCONV_SEXT) :
  503.                                 ((IRT_INTP<<5)|IRT_INT|IRCONV_TOBIT));
  504. }
  505. #endif

  507. /* -- Narrowing of arithmetic operators ----------------------------------- */

  509. /* Check whether a number fits into an int32_t (-0 is ok, too). */
  510. ‌static int numisint(lua_Number n)
  511. {
  512.   return (n == (lua_Number)lj_num2int(n));
  513. }

  515. /* Narrowing of arithmetic operations. */
  516. ‌TRef lj_opt_narrow_arith(jit_State *J, TRef rb, TRef rc,
  517.                          TValue *vb, TValue *vc, IROp op)
  518. {
  519.   if (tref_isstr(rb)) {
  520.     rb = emitir(IRTG(IR_STRTO, IRT_NUM), rb, 0);
  521.     lj_strscan_num(strV(vb), vb);
  522.   }
  523.   if (tref_isstr(rc)) {
  524.     rc = emitir(IRTG(IR_STRTO, IRT_NUM), rc, 0);
  525.     lj_strscan_num(strV(vc), vc);
  526.   }
  527.   /* Must not narrow MUL in non-DUALNUM variant, because it loses -0. */
  528.   if ((op >= IR_ADD && op <= (LJ_DUALNUM ? IR_MUL : IR_SUB)) &&
  529.       tref_isinteger(rb) && tref_isinteger(rc) &&
  530.       numisint(lj_vm_foldarith(numberVnum(vb), numberVnum(vc),
  531.                                (int)op - (int)IR_ADD)))
  532.     return emitir(IRTGI((int)op - (int)IR_ADD + (int)IR_ADDOV), rb, rc);
  533.   if (!tref_isnum(rb)) rb = emitir(IRTN(IR_CONV), rb, IRCONV_NUM_INT);
  534.   if (!tref_isnum(rc)) rc = emitir(IRTN(IR_CONV), rc, IRCONV_NUM_INT);
  535.   return emitir(IRTN(op), rb, rc);
  536. }

  538. /* Narrowing of unary minus operator. */
  539. ‌TRef lj_opt_narrow_unm(jit_State *J, TRef rc, TValue *vc)
  540. {
  541.   if (tref_isstr(rc)) {
  542.     rc = emitir(IRTG(IR_STRTO, IRT_NUM), rc, 0);
  543.     lj_strscan_num(strV(vc), vc);
  544.   }
  545.   if (tref_isinteger(rc)) {
  546.     if ((uint32_t)numberVint(vc) != 0x80000000u)
  547.       return emitir(IRTGI(IR_SUBOV), lj_ir_kint(J, 0), rc);
  548.     rc = emitir(IRTN(IR_CONV), rc, IRCONV_NUM_INT);
  549.   }
  550.   return emitir(IRTN(IR_NEG), rc, lj_ir_knum_neg(J));
  551. }

  553. /* Narrowing of modulo operator. */
  554. ‌TRef lj_opt_narrow_mod(jit_State *J, TRef rb, TRef rc, TValue *vc)
  555. {
  556.   TRef tmp;
  557.   if (tvisstr(vc) && !lj_strscan_num(strV(vc), vc))
  558.     lj_trace_err(J, LJ_TRERR_BADTYPE);
  559.   if ((LJ_DUALNUM || (J->flags & JIT_F_OPT_NARROW)) &&
  560.       tref_isinteger(rb) && tref_isinteger(rc) &&
  561.       (tvisint(vc) ? intV(vc) != 0 : !tviszero(vc))) {
  562.     emitir(IRTGI(IR_NE), rc, lj_ir_kint(J, 0));
  563.     return emitir(IRTI(IR_MOD), rb, rc);
  564.   }
  565.   /* b % c ==> b - floor(b/c)*c */
  566.   rb = lj_ir_tonum(J, rb);
  567.   rc = lj_ir_tonum(J, rc);
  568.   tmp = emitir(IRTN(IR_DIV), rb, rc);
  569.   tmp = emitir(IRTN(IR_FPMATH), tmp, IRFPM_FLOOR);
  570.   tmp = emitir(IRTN(IR_MUL), tmp, rc);
  571.   return emitir(IRTN(IR_SUB), rb, tmp);
  572. }

  574. /* Narrowing of power operator or math.pow. */
  575. ‌TRef lj_opt_narrow_pow(jit_State *J, TRef rb, TRef rc, TValue *vc)
  576. {
  577.   if (tvisstr(vc) && !lj_strscan_num(strV(vc), vc))
  578.     lj_trace_err(J, LJ_TRERR_BADTYPE);
  579.   /* Narrowing must be unconditional to preserve (-x)^i semantics. */
  580.   if (tvisint(vc) || numisint(numV(vc))) {
  581.     int checkrange = 0;
  582.     /* Split pow is faster for bigger exponents. But do this only for (+k)^i. */
  583.     if (tref_isk(rb) && (int32_t)ir_knum(IR(tref_ref(rb)))->u32.hi >= 0) {
  584.       int32_t k = numberVint(vc);
  585.       if (!(k >= -65536 && k <= 65536)) goto split_pow;
  586.       checkrange = 1;
  587.     }
  588.     if (!tref_isinteger(rc)) {
  589.       if (tref_isstr(rc))
  590.         rc = emitir(IRTG(IR_STRTO, IRT_NUM), rc, 0);
  591.       /* Guarded conversion to integer! */
  592.       rc = emitir(IRTGI(IR_CONV), rc, IRCONV_INT_NUM|IRCONV_CHECK);
  593.     }
  594.     if (checkrange && !tref_isk(rc)) {  /* Range guard: -65536 <= i <= 65536 */
  595.       TRef tmp = emitir(IRTI(IR_ADD), rc, lj_ir_kint(J, 65536));
  596.       emitir(IRTGI(IR_ULE), tmp, lj_ir_kint(J, 2*65536));
  597.     }
  598.     return emitir(IRTN(IR_POW), rb, rc);
  599.   }
  600. split_pow:
  601.   /* FOLD covers most cases, but some are easier to do here. */
  602.   if (tref_isk(rb) && tvispone(ir_knum(IR(tref_ref(rb)))))
  603.     return rb;  /* 1 ^ x ==> 1 */
  604.   rc = lj_ir_tonum(J, rc);
  605.   if (tref_isk(rc) && ir_knum(IR(tref_ref(rc)))->n == 0.5)
  606.     return emitir(IRTN(IR_FPMATH), rb, IRFPM_SQRT);  /* x ^ 0.5 ==> sqrt(x) */
  607.   /* Split up b^c into exp2(c*log2(b)). Assembler may rejoin later. */
  608.   rb = emitir(IRTN(IR_FPMATH), rb, IRFPM_LOG2);
  609.   rc = emitir(IRTN(IR_MUL), rb, rc);
  610.   return emitir(IRTN(IR_FPMATH), rc, IRFPM_EXP2);
  611. }

  613. /* -- Predictive narrowing of induction variables ------------------------- */

  615. /* Narrow a single runtime value. */
  616. ‌static int narrow_forl(jit_State *J, cTValue *o)
  617. {
  618.   if (tvisint(o)) return 1;
  619.   if (LJ_DUALNUM || (J->flags & JIT_F_OPT_NARROW)) return numisint(numV(o));
  620.   return 0;
  621. }

  623. /* Narrow the FORL index type by looking at the runtime values. */
  624. ‌IRType lj_opt_narrow_forl(jit_State *J, cTValue *tv)
  625. {
  626.   lua_assert(tvisnumber(&tv[FORL_IDX]) &&
  627.              tvisnumber(&tv[FORL_STOP]) &&
  628.              tvisnumber(&tv[FORL_STEP]));
  629.   /* Narrow only if the runtime values of start/stop/step are all integers. */
  630.   if (narrow_forl(J, &tv[FORL_IDX]) &&
  631.       narrow_forl(J, &tv[FORL_STOP]) &&
  632.       narrow_forl(J, &tv[FORL_STEP])) {
  633.     /* And if the loop index can't possibly overflow. */
  634.     lua_Number step = numberVnum(&tv[FORL_STEP]);
  635.     lua_Number sum = numberVnum(&tv[FORL_STOP]) + step;
  636.     if (0 <= step ? (sum <= 2147483647.0) : (sum >= -2147483648.0))
  637.       return IRT_INT;
  638.   }
  639.   return IRT_NUM;
  640. }

  642. ‌#undef IR
  643. ‌#undef fins
  644. ‌#undef emitir
  645. ‌#undef emitir_raw

  647. #endif

One Level Up Top Level