1/*
2** NARROW: Narrowing of numbers to integers (double to int32_t).
3** STRIPOV: Stripping of overflow checks.
4** Copyright (C) 2005-2014 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*/
190enum {
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
197typedef 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. */
204typedef 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;
213
214/* Lookup a reference in the backpropagation cache. */
215static 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}
227
228/* Add an entry to the backpropagation cache. */
229static 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}
238
239/* Backpropagate overflow stripping. */
240static 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}
258
259/* Backpropagate narrowing conversion. Return number of needed conversions. */
260static 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;
265
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 }
296
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 }
310
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 }
344
345 /* Otherwise add a conversion. */
346 *nc->sp++ = NARROWINS(NARROW_CONV, ref);
347 return 1;
348}
349
350/* Emit the conversions collected during backpropagation. */
351static 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}
397
398/* Narrow a type conversion of an arithmetic operation. */
399TRef 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}
419
420/* -- Narrowing of implicit conversions ----------------------------------- */
421
422/* Recursively strip overflow checks. */
423static 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}
445
446/* Narrow array index. */
447TRef 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}
460
461/* Narrow conversion to integer operand (overflow undefined). */
462TRef 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}
476
477/* Narrow conversion to bitop operand (overflow wrapped). */
478TRef 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}
492
493#if LJ_HASFFI
494/* Narrow C array index (overflow undefined). */
495TRef 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,
500 (IRT_INTP<<5)|IRT_NUM|IRCONV_TRUNC|IRCONV_ANY);
501 /* Undefined overflow semantics allow stripping of ADDOV, SUBOV and MULOV. */
502 return narrow_stripov(J, tr, IR_MULOV,
503 LJ_64 ? ((IRT_INTP<<5)|IRT_INT|IRCONV_SEXT) :
504 ((IRT_INTP<<5)|IRT_INT|IRCONV_TOBIT));
505}
506#endif
507
508/* -- Narrowing of arithmetic operators ----------------------------------- */
509
510/* Check whether a number fits into an int32_t (-0 is ok, too). */
511static int numisint(lua_Number n)
512{
513 return (n == (lua_Number)lj_num2int(n));
514}
515
516/* Narrowing of arithmetic operations. */
517TRef lj_opt_narrow_arith(jit_State *J, TRef rb, TRef rc,
518 TValue *vb, TValue *vc, IROp op)
519{
520 if (tref_isstr(rb)) {
521 rb = emitir(IRTG(IR_STRTO, IRT_NUM), rb, 0);
522 lj_strscan_num(strV(vb), vb);
523 }
524 if (tref_isstr(rc)) {
525 rc = emitir(IRTG(IR_STRTO, IRT_NUM), rc, 0);
526 lj_strscan_num(strV(vc), vc);
527 }
528 /* Must not narrow MUL in non-DUALNUM variant, because it loses -0. */
529 if ((op >= IR_ADD && op <= (LJ_DUALNUM ? IR_MUL : IR_SUB)) &&
530 tref_isinteger(rb) && tref_isinteger(rc) &&
531 numisint(lj_vm_foldarith(numberVnum(vb), numberVnum(vc),
532 (int)op - (int)IR_ADD)))
533 return emitir(IRTGI((int)op - (int)IR_ADD + (int)IR_ADDOV), rb, rc);
534 if (!tref_isnum(rb)) rb = emitir(IRTN(IR_CONV), rb, IRCONV_NUM_INT);
535 if (!tref_isnum(rc)) rc = emitir(IRTN(IR_CONV), rc, IRCONV_NUM_INT);
536 return emitir(IRTN(op), rb, rc);
537}
538
539/* Narrowing of unary minus operator. */
540TRef lj_opt_narrow_unm(jit_State *J, TRef rc, TValue *vc)
541{
542 if (tref_isstr(rc)) {
543 rc = emitir(IRTG(IR_STRTO, IRT_NUM), rc, 0);
544 lj_strscan_num(strV(vc), vc);
545 }
546 if (tref_isinteger(rc)) {
547 if ((uint32_t)numberVint(vc) != 0x80000000u)
548 return emitir(IRTGI(IR_SUBOV), lj_ir_kint(J, 0), rc);
549 rc = emitir(IRTN(IR_CONV), rc, IRCONV_NUM_INT);
550 }
551 return emitir(IRTN(IR_NEG), rc, lj_ir_knum_neg(J));
552}
553
554/* Narrowing of modulo operator. */
555TRef lj_opt_narrow_mod(jit_State *J, TRef rb, TRef rc, TValue *vc)
556{
557 TRef tmp;
558 if (tvisstr(vc) && !lj_strscan_num(strV(vc), vc))
559 lj_trace_err(J, LJ_TRERR_BADTYPE);
560 if ((LJ_DUALNUM || (J->flags & JIT_F_OPT_NARROW)) &&
561 tref_isinteger(rb) && tref_isinteger(rc) &&
562 (tvisint(vc) ? intV(vc) != 0 : !tviszero(vc))) {
563 emitir(IRTGI(IR_NE), rc, lj_ir_kint(J, 0));
564 return emitir(IRTI(IR_MOD), rb, rc);
565 }
566 /* b % c ==> b - floor(b/c)*c */
567 rb = lj_ir_tonum(J, rb);
568 rc = lj_ir_tonum(J, rc);
569 tmp = emitir(IRTN(IR_DIV), rb, rc);
570 tmp = emitir(IRTN(IR_FPMATH), tmp, IRFPM_FLOOR);
571 tmp = emitir(IRTN(IR_MUL), tmp, rc);
572 return emitir(IRTN(IR_SUB), rb, tmp);
573}
574
575/* Narrowing of power operator or math.pow. */
576TRef lj_opt_narrow_pow(jit_State *J, TRef rb, TRef rc, TValue *vc)
577{
578 if (tvisstr(vc) && !lj_strscan_num(strV(vc), vc))
579 lj_trace_err(J, LJ_TRERR_BADTYPE);
580 /* Narrowing must be unconditional to preserve (-x)^i semantics. */
581 if (tvisint(vc) || numisint(numV(vc))) {
582 int checkrange = 0;
583 /* Split pow is faster for bigger exponents. But do this only for (+k)^i. */
584 if (tref_isk(rb) && (int32_t)ir_knum(IR(tref_ref(rb)))->u32.hi >= 0) {
585 int32_t k = numberVint(vc);
586 if (!(k >= -65536 && k <= 65536)) goto split_pow;
587 checkrange = 1;
588 }
589 if (!tref_isinteger(rc)) {
590 if (tref_isstr(rc))
591 rc = emitir(IRTG(IR_STRTO, IRT_NUM), rc, 0);
592 /* Guarded conversion to integer! */
593 rc = emitir(IRTGI(IR_CONV), rc, IRCONV_INT_NUM|IRCONV_CHECK);
594 }
595 if (checkrange && !tref_isk(rc)) { /* Range guard: -65536 <= i <= 65536 */
596 TRef tmp = emitir(IRTI(IR_ADD), rc, lj_ir_kint(J, 65536));
597 emitir(IRTGI(IR_ULE), tmp, lj_ir_kint(J, 2*65536));
598 }
599 return emitir(IRTN(IR_POW), rb, rc);
600 }
601split_pow:
602 /* FOLD covers most cases, but some are easier to do here. */
603 if (tref_isk(rb) && tvispone(ir_knum(IR(tref_ref(rb)))))
604 return rb; /* 1 ^ x ==> 1 */
605 rc = lj_ir_tonum(J, rc);
606 if (tref_isk(rc) && ir_knum(IR(tref_ref(rc)))->n == 0.5)
607 return emitir(IRTN(IR_FPMATH), rb, IRFPM_SQRT); /* x ^ 0.5 ==> sqrt(x) */
608 /* Split up b^c into exp2(c*log2(b)). Assembler may rejoin later. */
609 rb = emitir(IRTN(IR_FPMATH), rb, IRFPM_LOG2);
610 rc = emitir(IRTN(IR_MUL), rb, rc);
611 return emitir(IRTN(IR_FPMATH), rc, IRFPM_EXP2);
612}
613
614/* -- Predictive narrowing of induction variables ------------------------- */
615
616/* Narrow a single runtime value. */
617static int narrow_forl(jit_State *J, cTValue *o)
618{
619 if (tvisint(o)) return 1;
620 if (LJ_DUALNUM || (J->flags & JIT_F_OPT_NARROW)) return numisint(numV(o));
621 return 0;
622}
623
624/* Narrow the FORL index type by looking at the runtime values. */
625IRType lj_opt_narrow_forl(jit_State *J, cTValue *tv)
626{
627 lua_assert(tvisnumber(&tv[FORL_IDX]) &&
628 tvisnumber(&tv[FORL_STOP]) &&
629 tvisnumber(&tv[FORL_STEP]));
630 /* Narrow only if the runtime values of start/stop/step are all integers. */
631 if (narrow_forl(J, &tv[FORL_IDX]) &&
632 narrow_forl(J, &tv[FORL_STOP]) &&
633 narrow_forl(J, &tv[FORL_STEP])) {
634 /* And if the loop index can't possibly overflow. */
635 lua_Number step = numberVnum(&tv[FORL_STEP]);
636 lua_Number sum = numberVnum(&tv[FORL_STOP]) + step;
637 if (0 <= step ? (sum <= 2147483647.0) : (sum >= -2147483648.0))
638 return IRT_INT;
639 }
640 return IRT_NUM;
641}
642
643#undef IR
644#undef fins
645#undef emitir
646#undef emitir_raw
647
648#endif
649