Mercurial

comparison third_party/luajit/src/lj_opt_narrow.c @ 186:8cf4ec5e2191 hg-web

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fixed merge conflict.
author MrJuneJune <me@mrjunejune.com>
date Fri, 23 Jan 2026 22:38:59 -0800
parents 94705b5986b3
children
comparison
equal deleted inserted replaced
176:fed99fc04e12 186:8cf4ec5e2191
1 /*
2 ** NARROW: Narrowing of numbers to integers (double to int32_t).
3 ** STRIPOV: Stripping of overflow checks.
4 ** Copyright (C) 2005-2023 Mike Pall. See Copyright Notice in luajit.h
5 */
6
7 #define lj_opt_narrow_c
8 #define LUA_CORE
9
10 #include "lj_obj.h"
11
12 #if LJ_HASJIT
13
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"
21
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 */
91
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)
95
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))
98
99 #define emitir_raw(ot, a, b) (lj_ir_set(J, (ot), (a), (b)), lj_ir_emit(J))
100
101 /* -- Elimination of narrowing type conversions --------------------------- */
102
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 */
181
182 /* Maximum backpropagation depth and maximum stack size. */
183 #define NARROW_MAX_BACKPROP 100
184 #define NARROW_MAX_STACK 256
185
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 };
196
197 typedef uint32_t NarrowIns;
198
199 #define NARROWINS(op, ref) (((op) << 16) + (ref))
200 #define narrow_op(ins) ((IROpT)((ins) >> 16))
201 #define narrow_ref(ins) ((IRRef1)(ins))
202
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 IRRef mode; /* Conversion mode (IRCONV_*). */
209 IRType t; /* Destination type: IRT_INT or IRT_I64. */
210 NarrowIns stack[NARROW_MAX_STACK]; /* Stack holding stack-machine code. */
211 } NarrowConv;
212
213 /* Lookup a reference in the backpropagation cache. */
214 static BPropEntry *narrow_bpc_get(jit_State *J, IRRef1 key, IRRef mode)
215 {
216 ptrdiff_t i;
217 for (i = 0; i < BPROP_SLOTS; i++) {
218 BPropEntry *bp = &J->bpropcache[i];
219 /* Stronger checks are ok, too. */
220 if (bp->key == key && bp->mode >= mode &&
221 ((bp->mode ^ mode) & IRCONV_MODEMASK) == 0)
222 return bp;
223 }
224 return NULL;
225 }
226
227 /* Add an entry to the backpropagation cache. */
228 static void narrow_bpc_set(jit_State *J, IRRef1 key, IRRef1 val, IRRef mode)
229 {
230 uint32_t slot = J->bpropslot;
231 BPropEntry *bp = &J->bpropcache[slot];
232 J->bpropslot = (slot + 1) & (BPROP_SLOTS-1);
233 bp->key = key;
234 bp->val = val;
235 bp->mode = mode;
236 }
237
238 /* Backpropagate overflow stripping. */
239 static void narrow_stripov_backprop(NarrowConv *nc, IRRef ref, int depth)
240 {
241 jit_State *J = nc->J;
242 IRIns *ir = IR(ref);
243 if (ir->o == IR_ADDOV || ir->o == IR_SUBOV ||
244 (ir->o == IR_MULOV && (nc->mode & IRCONV_CONVMASK) == IRCONV_ANY)) {
245 BPropEntry *bp = narrow_bpc_get(nc->J, ref, IRCONV_TOBIT);
246 if (bp) {
247 ref = bp->val;
248 } else if (++depth < NARROW_MAX_BACKPROP && nc->sp < nc->maxsp) {
249 NarrowIns *savesp = nc->sp;
250 narrow_stripov_backprop(nc, ir->op1, depth);
251 if (nc->sp < nc->maxsp) {
252 narrow_stripov_backprop(nc, ir->op2, depth);
253 if (nc->sp < nc->maxsp) {
254 *nc->sp++ = NARROWINS(IRT(ir->o - IR_ADDOV + IR_ADD, IRT_INT), ref);
255 return;
256 }
257 }
258 nc->sp = savesp; /* Path too deep, need to backtrack. */
259 }
260 }
261 *nc->sp++ = NARROWINS(NARROW_REF, ref);
262 }
263
264 /* Backpropagate narrowing conversion. Return number of needed conversions. */
265 static int narrow_conv_backprop(NarrowConv *nc, IRRef ref, int depth)
266 {
267 jit_State *J = nc->J;
268 IRIns *ir = IR(ref);
269 IRRef cref;
270
271 if (nc->sp >= nc->maxsp) return 10; /* Path too deep. */
272
273 /* Check the easy cases first. */
274 if (ir->o == IR_CONV && (ir->op2 & IRCONV_SRCMASK) == IRT_INT) {
275 if ((nc->mode & IRCONV_CONVMASK) <= IRCONV_ANY)
276 narrow_stripov_backprop(nc, ir->op1, depth+1);
277 else
278 *nc->sp++ = NARROWINS(NARROW_REF, ir->op1); /* Undo conversion. */
279 if (nc->t == IRT_I64)
280 *nc->sp++ = NARROWINS(NARROW_SEXT, 0); /* Sign-extend integer. */
281 return 0;
282 } else if (ir->o == IR_KNUM) { /* Narrow FP constant. */
283 lua_Number n = ir_knum(ir)->n;
284 if ((nc->mode & IRCONV_CONVMASK) == IRCONV_TOBIT) {
285 /* Allows a wider range of constants. */
286 int64_t k64 = (int64_t)n;
287 if (n == (lua_Number)k64) { /* Only if const doesn't lose precision. */
288 *nc->sp++ = NARROWINS(NARROW_INT, 0);
289 *nc->sp++ = (NarrowIns)k64; /* But always truncate to 32 bits. */
290 return 0;
291 }
292 } else {
293 int32_t k = lj_num2int(n);
294 /* Only if constant is a small integer. */
295 if (checki16(k) && n == (lua_Number)k) {
296 *nc->sp++ = NARROWINS(NARROW_INT, 0);
297 *nc->sp++ = (NarrowIns)k;
298 return 0;
299 }
300 }
301 return 10; /* Never narrow other FP constants (this is rare). */
302 }
303
304 /* Try to CSE the conversion. Stronger checks are ok, too. */
305 cref = J->chain[fins->o];
306 while (cref > ref) {
307 IRIns *cr = IR(cref);
308 if (cr->op1 == ref &&
309 (fins->o == IR_TOBIT ||
310 ((cr->op2 & IRCONV_MODEMASK) == (nc->mode & IRCONV_MODEMASK) &&
311 irt_isguard(cr->t) >= irt_isguard(fins->t)))) {
312 *nc->sp++ = NARROWINS(NARROW_REF, cref);
313 return 0; /* Already there, no additional conversion needed. */
314 }
315 cref = cr->prev;
316 }
317
318 /* Backpropagate across ADD/SUB. */
319 if (ir->o == IR_ADD || ir->o == IR_SUB) {
320 /* Try cache lookup first. */
321 IRRef mode = nc->mode;
322 BPropEntry *bp;
323 /* Inner conversions need a stronger check. */
324 if ((mode & IRCONV_CONVMASK) == IRCONV_INDEX && depth > 0)
325 mode += IRCONV_CHECK-IRCONV_INDEX;
326 bp = narrow_bpc_get(nc->J, (IRRef1)ref, mode);
327 if (bp) {
328 *nc->sp++ = NARROWINS(NARROW_REF, bp->val);
329 return 0;
330 } else if (nc->t == IRT_I64) {
331 /* Try sign-extending from an existing (checked) conversion to int. */
332 mode = (IRT_INT<<5)|IRT_NUM|IRCONV_INDEX;
333 bp = narrow_bpc_get(nc->J, (IRRef1)ref, mode);
334 if (bp) {
335 *nc->sp++ = NARROWINS(NARROW_REF, bp->val);
336 *nc->sp++ = NARROWINS(NARROW_SEXT, 0);
337 return 0;
338 }
339 }
340 if (++depth < NARROW_MAX_BACKPROP && nc->sp < nc->maxsp) {
341 NarrowIns *savesp = nc->sp;
342 int count = narrow_conv_backprop(nc, ir->op1, depth);
343 count += narrow_conv_backprop(nc, ir->op2, depth);
344 if (count <= 1) { /* Limit total number of conversions. */
345 *nc->sp++ = NARROWINS(IRT(ir->o, nc->t), ref);
346 return count;
347 }
348 nc->sp = savesp; /* Too many conversions, need to backtrack. */
349 }
350 }
351
352 /* Otherwise add a conversion. */
353 *nc->sp++ = NARROWINS(NARROW_CONV, ref);
354 return 1;
355 }
356
357 /* Emit the conversions collected during backpropagation. */
358 static IRRef narrow_conv_emit(jit_State *J, NarrowConv *nc)
359 {
360 /* The fins fields must be saved now -- emitir() overwrites them. */
361 IROpT guardot = irt_isguard(fins->t) ? IRTG(IR_ADDOV-IR_ADD, 0) : 0;
362 IROpT convot = fins->ot;
363 IRRef1 convop2 = fins->op2;
364 NarrowIns *next = nc->stack; /* List of instructions from backpropagation. */
365 NarrowIns *last = nc->sp;
366 NarrowIns *sp = nc->stack; /* Recycle the stack to store operands. */
367 while (next < last) { /* Simple stack machine to process the ins. list. */
368 NarrowIns ref = *next++;
369 IROpT op = narrow_op(ref);
370 if (op == NARROW_REF) {
371 *sp++ = ref;
372 } else if (op == NARROW_CONV) {
373 *sp++ = emitir_raw(convot, ref, convop2); /* Raw emit avoids a loop. */
374 } else if (op == NARROW_SEXT) {
375 lj_assertJ(sp >= nc->stack+1, "stack underflow");
376 sp[-1] = emitir(IRT(IR_CONV, IRT_I64), sp[-1],
377 (IRT_I64<<5)|IRT_INT|IRCONV_SEXT);
378 } else if (op == NARROW_INT) {
379 lj_assertJ(next < last, "missing arg to NARROW_INT");
380 *sp++ = nc->t == IRT_I64 ?
381 lj_ir_kint64(J, (int64_t)(int32_t)*next++) :
382 lj_ir_kint(J, *next++);
383 } else { /* Regular IROpT. Pops two operands and pushes one result. */
384 IRRef mode = nc->mode;
385 lj_assertJ(sp >= nc->stack+2, "stack underflow");
386 sp--;
387 /* Omit some overflow checks for array indexing. See comments above. */
388 if ((mode & IRCONV_CONVMASK) == IRCONV_INDEX) {
389 if (next == last && irref_isk(narrow_ref(sp[0])) &&
390 (uint32_t)IR(narrow_ref(sp[0]))->i + 0x40000000u < 0x80000000u)
391 guardot = 0;
392 else /* Otherwise cache a stronger check. */
393 mode += IRCONV_CHECK-IRCONV_INDEX;
394 }
395 sp[-1] = emitir(op+guardot, sp[-1], sp[0]);
396 /* Add to cache. */
397 if (narrow_ref(ref))
398 narrow_bpc_set(J, narrow_ref(ref), narrow_ref(sp[-1]), mode);
399 }
400 }
401 lj_assertJ(sp == nc->stack+1, "stack misalignment");
402 return nc->stack[0];
403 }
404
405 /* Narrow a type conversion of an arithmetic operation. */
406 TRef LJ_FASTCALL lj_opt_narrow_convert(jit_State *J)
407 {
408 if ((J->flags & JIT_F_OPT_NARROW)) {
409 NarrowConv nc;
410 nc.J = J;
411 nc.sp = nc.stack;
412 nc.maxsp = &nc.stack[NARROW_MAX_STACK-4];
413 nc.t = irt_type(fins->t);
414 if (fins->o == IR_TOBIT) {
415 nc.mode = IRCONV_TOBIT; /* Used only in the backpropagation cache. */
416 } else {
417 nc.mode = fins->op2;
418 }
419 if (narrow_conv_backprop(&nc, fins->op1, 0) <= 1)
420 return narrow_conv_emit(J, &nc);
421 }
422 return NEXTFOLD;
423 }
424
425 /* -- Narrowing of implicit conversions ----------------------------------- */
426
427 /* Recursively strip overflow checks. */
428 static TRef narrow_stripov(jit_State *J, TRef tr, int lastop, IRRef mode)
429 {
430 IRRef ref = tref_ref(tr);
431 IRIns *ir = IR(ref);
432 int op = ir->o;
433 if (op >= IR_ADDOV && op <= lastop) {
434 BPropEntry *bp = narrow_bpc_get(J, ref, mode);
435 if (bp) {
436 return TREF(bp->val, irt_t(IR(bp->val)->t));
437 } else {
438 IRRef op1 = ir->op1, op2 = ir->op2; /* The IR may be reallocated. */
439 op1 = narrow_stripov(J, op1, lastop, mode);
440 op2 = narrow_stripov(J, op2, lastop, mode);
441 tr = emitir(IRT(op - IR_ADDOV + IR_ADD,
442 ((mode & IRCONV_DSTMASK) >> IRCONV_DSH)), op1, op2);
443 narrow_bpc_set(J, ref, tref_ref(tr), mode);
444 }
445 } else if (LJ_64 && (mode & IRCONV_SEXT) && !irt_is64(ir->t)) {
446 tr = emitir(IRT(IR_CONV, IRT_INTP), tr, mode);
447 }
448 return tr;
449 }
450
451 /* Narrow array index. */
452 TRef LJ_FASTCALL lj_opt_narrow_index(jit_State *J, TRef tr)
453 {
454 IRIns *ir;
455 lj_assertJ(tref_isnumber(tr), "expected number type");
456 if (tref_isnum(tr)) /* Conversion may be narrowed, too. See above. */
457 return emitir(IRTGI(IR_CONV), tr, IRCONV_INT_NUM|IRCONV_INDEX);
458 /* Omit some overflow checks for array indexing. See comments above. */
459 ir = IR(tref_ref(tr));
460 if ((ir->o == IR_ADDOV || ir->o == IR_SUBOV) && irref_isk(ir->op2) &&
461 (uint32_t)IR(ir->op2)->i + 0x40000000u < 0x80000000u)
462 return emitir(IRTI(ir->o - IR_ADDOV + IR_ADD), ir->op1, ir->op2);
463 return tr;
464 }
465
466 /* Narrow conversion to integer operand (overflow undefined). */
467 TRef LJ_FASTCALL lj_opt_narrow_toint(jit_State *J, TRef tr)
468 {
469 if (tref_isstr(tr))
470 tr = emitir(IRTG(IR_STRTO, IRT_NUM), tr, 0);
471 if (tref_isnum(tr)) /* Conversion may be narrowed, too. See above. */
472 return emitir(IRTI(IR_CONV), tr, IRCONV_INT_NUM|IRCONV_ANY);
473 if (!tref_isinteger(tr))
474 lj_trace_err(J, LJ_TRERR_BADTYPE);
475 /*
476 ** Undefined overflow semantics allow stripping of ADDOV, SUBOV and MULOV.
477 ** Use IRCONV_TOBIT for the cache entries, since the semantics are the same.
478 */
479 return narrow_stripov(J, tr, IR_MULOV, (IRT_INT<<5)|IRT_INT|IRCONV_TOBIT);
480 }
481
482 /* Narrow conversion to bitop operand (overflow wrapped). */
483 TRef LJ_FASTCALL lj_opt_narrow_tobit(jit_State *J, TRef tr)
484 {
485 if (tref_isstr(tr))
486 tr = emitir(IRTG(IR_STRTO, IRT_NUM), tr, 0);
487 if (tref_isnum(tr)) /* Conversion may be narrowed, too. See above. */
488 return emitir(IRTI(IR_TOBIT), tr, lj_ir_knum_tobit(J));
489 if (!tref_isinteger(tr))
490 lj_trace_err(J, LJ_TRERR_BADTYPE);
491 /*
492 ** Wrapped overflow semantics allow stripping of ADDOV and SUBOV.
493 ** MULOV cannot be stripped due to precision widening.
494 */
495 return narrow_stripov(J, tr, IR_SUBOV, (IRT_INT<<5)|IRT_INT|IRCONV_TOBIT);
496 }
497
498 #if LJ_HASFFI
499 /* Narrow C array index (overflow undefined). */
500 TRef LJ_FASTCALL lj_opt_narrow_cindex(jit_State *J, TRef tr)
501 {
502 lj_assertJ(tref_isnumber(tr), "expected number type");
503 if (tref_isnum(tr))
504 return emitir(IRT(IR_CONV, IRT_INTP), tr, (IRT_INTP<<5)|IRT_NUM|IRCONV_ANY);
505 /* Undefined overflow semantics allow stripping of ADDOV, SUBOV and MULOV. */
506 return narrow_stripov(J, tr, IR_MULOV,
507 LJ_64 ? ((IRT_INTP<<5)|IRT_INT|IRCONV_SEXT) :
508 ((IRT_INTP<<5)|IRT_INT|IRCONV_TOBIT));
509 }
510 #endif
511
512 /* -- Narrowing of arithmetic operators ----------------------------------- */
513
514 /* Check whether a number fits into an int32_t (-0 is ok, too). */
515 static int numisint(lua_Number n)
516 {
517 return (n == (lua_Number)lj_num2int(n));
518 }
519
520 /* Convert string to number. Error out for non-numeric string values. */
521 static TRef conv_str_tonum(jit_State *J, TRef tr, TValue *o)
522 {
523 if (tref_isstr(tr)) {
524 tr = emitir(IRTG(IR_STRTO, IRT_NUM), tr, 0);
525 /* Would need an inverted STRTO for this rare and useless case. */
526 if (!lj_strscan_num(strV(o), o)) /* Convert in-place. Value used below. */
527 lj_trace_err(J, LJ_TRERR_BADTYPE); /* Punt if non-numeric. */
528 }
529 return tr;
530 }
531
532 /* Narrowing of arithmetic operations. */
533 TRef lj_opt_narrow_arith(jit_State *J, TRef rb, TRef rc,
534 TValue *vb, TValue *vc, IROp op)
535 {
536 rb = conv_str_tonum(J, rb, vb);
537 rc = conv_str_tonum(J, rc, vc);
538 /* Must not narrow MUL in non-DUALNUM variant, because it loses -0. */
539 if ((op >= IR_ADD && op <= (LJ_DUALNUM ? IR_MUL : IR_SUB)) &&
540 tref_isinteger(rb) && tref_isinteger(rc) &&
541 numisint(lj_vm_foldarith(numberVnum(vb), numberVnum(vc),
542 (int)op - (int)IR_ADD)))
543 return emitir(IRTGI((int)op - (int)IR_ADD + (int)IR_ADDOV), rb, rc);
544 if (!tref_isnum(rb)) rb = emitir(IRTN(IR_CONV), rb, IRCONV_NUM_INT);
545 if (!tref_isnum(rc)) rc = emitir(IRTN(IR_CONV), rc, IRCONV_NUM_INT);
546 return emitir(IRTN(op), rb, rc);
547 }
548
549 /* Narrowing of unary minus operator. */
550 TRef lj_opt_narrow_unm(jit_State *J, TRef rc, TValue *vc)
551 {
552 rc = conv_str_tonum(J, rc, vc);
553 if (tref_isinteger(rc)) {
554 uint32_t k = (uint32_t)numberVint(vc);
555 if ((LJ_DUALNUM || k != 0) && k != 0x80000000u) {
556 TRef zero = lj_ir_kint(J, 0);
557 if (!LJ_DUALNUM)
558 emitir(IRTGI(IR_NE), rc, zero);
559 return emitir(IRTGI(IR_SUBOV), zero, rc);
560 }
561 rc = emitir(IRTN(IR_CONV), rc, IRCONV_NUM_INT);
562 }
563 return emitir(IRTN(IR_NEG), rc, lj_ir_ksimd(J, LJ_KSIMD_NEG));
564 }
565
566 /* Narrowing of modulo operator. */
567 TRef lj_opt_narrow_mod(jit_State *J, TRef rb, TRef rc, TValue *vb, TValue *vc)
568 {
569 TRef tmp;
570 rb = conv_str_tonum(J, rb, vb);
571 rc = conv_str_tonum(J, rc, vc);
572 if ((LJ_DUALNUM || (J->flags & JIT_F_OPT_NARROW)) &&
573 tref_isinteger(rb) && tref_isinteger(rc) &&
574 (tvisint(vc) ? intV(vc) != 0 : !tviszero(vc))) {
575 emitir(IRTGI(IR_NE), rc, lj_ir_kint(J, 0));
576 return emitir(IRTI(IR_MOD), rb, rc);
577 }
578 /* b % c ==> b - floor(b/c)*c */
579 rb = lj_ir_tonum(J, rb);
580 rc = lj_ir_tonum(J, rc);
581 tmp = emitir(IRTN(IR_DIV), rb, rc);
582 tmp = emitir(IRTN(IR_FPMATH), tmp, IRFPM_FLOOR);
583 tmp = emitir(IRTN(IR_MUL), tmp, rc);
584 return emitir(IRTN(IR_SUB), rb, tmp);
585 }
586
587 /* -- Predictive narrowing of induction variables ------------------------- */
588
589 /* Narrow a single runtime value. */
590 static int narrow_forl(jit_State *J, cTValue *o)
591 {
592 if (tvisint(o)) return 1;
593 if (LJ_DUALNUM || (J->flags & JIT_F_OPT_NARROW)) return numisint(numV(o));
594 return 0;
595 }
596
597 /* Narrow the FORL index type by looking at the runtime values. */
598 IRType lj_opt_narrow_forl(jit_State *J, cTValue *tv)
599 {
600 lj_assertJ(tvisnumber(&tv[FORL_IDX]) &&
601 tvisnumber(&tv[FORL_STOP]) &&
602 tvisnumber(&tv[FORL_STEP]),
603 "expected number types");
604 /* Narrow only if the runtime values of start/stop/step are all integers. */
605 if (narrow_forl(J, &tv[FORL_IDX]) &&
606 narrow_forl(J, &tv[FORL_STOP]) &&
607 narrow_forl(J, &tv[FORL_STEP])) {
608 /* And if the loop index can't possibly overflow. */
609 lua_Number step = numberVnum(&tv[FORL_STEP]);
610 lua_Number sum = numberVnum(&tv[FORL_STOP]) + step;
611 if (0 <= step ? (sum <= 2147483647.0) : (sum >= -2147483648.0))
612 return IRT_INT;
613 }
614 return IRT_NUM;
615 }
616
617 #undef IR
618 #undef fins
619 #undef emitir
620 #undef emitir_raw
621
622 #endif