luna - luajit/src/lj_opt

   1/*
   2** FOLD: Constant Folding, Algebraic Simplifications and Reassociation.
   3** ABCelim: Array Bounds Check Elimination.
   4** CSE: Common-Subexpression Elimination.
   5** Copyright (C) 2005-2026 Mike Pall. See Copyright Notice in luajit.h
   6*/
   7
   8#define lj_opt_fold_c
   9#define LUA_CORE
  10
  11#include <math.h>
  12
  13#include "lj_obj.h"
  14
  15#if LJ_HASJIT
  16
  17#include "lj_buf.h"
  18#include "lj_str.h"
  19#include "lj_tab.h"
  20#include "lj_ir.h"
  21#include "lj_jit.h"
  22#include "lj_ircall.h"
  23#include "lj_iropt.h"
  24#include "lj_trace.h"
  25#if LJ_HASFFI
  26#include "lj_ctype.h"
  27#include "lj_carith.h"
  28#endif
  29#include "lj_vm.h"
  30#include "lj_strscan.h"
  31#include "lj_strfmt.h"
  32
  33/* Here's a short description how the FOLD engine processes instructions:
  34**
  35** The FOLD engine receives a single instruction stored in fins (J->fold.ins).
  36** The instruction and its operands are used to select matching fold rules.
  37** These are applied iteratively until a fixed point is reached.
  38**
  39** The 8 bit opcode of the instruction itself plus the opcodes of the
  40** two instructions referenced by its operands form a 24 bit key
  41** 'ins left right' (unused operands -> 0, literals -> lowest 8 bits).
  42**
  43** This key is used for partial matching against the fold rules. The
  44** left/right operand fields of the key are successively masked with
  45** the 'any' wildcard, from most specific to least specific:
  46**
  47**   ins left right
  48**   ins any  right
  49**   ins left any
  50**   ins any  any
  51**
  52** The masked key is used to lookup a matching fold rule in a semi-perfect
  53** hash table. If a matching rule is found, the related fold function is run.
  54** Multiple rules can share the same fold function. A fold rule may return
  55** one of several special values:
  56**
  57** - NEXTFOLD means no folding was applied, because an additional test
  58**   inside the fold function failed. Matching continues against less
  59**   specific fold rules. Finally the instruction is passed on to CSE.
  60**
  61** - RETRYFOLD means the instruction was modified in-place. Folding is
  62**   retried as if this instruction had just been received.
  63**
  64** All other return values are terminal actions -- no further folding is
  65** applied:
  66**
  67** - INTFOLD(i) returns a reference to the integer constant i.
  68**
  69** - LEFTFOLD and RIGHTFOLD return the left/right operand reference
  70**   without emitting an instruction.
  71**
  72** - CSEFOLD and EMITFOLD pass the instruction directly to CSE or emit
  73**   it without passing through any further optimizations.
  74**
  75** - FAILFOLD, DROPFOLD and CONDFOLD only apply to instructions which have
  76**   no result (e.g. guarded assertions): FAILFOLD means the guard would
  77**   always fail, i.e. the current trace is pointless. DROPFOLD means
  78**   the guard is always true and has been eliminated. CONDFOLD is a
  79**   shortcut for FAILFOLD + cond (i.e. drop if true, otherwise fail).
  80**
  81** - Any other return value is interpreted as an IRRef or TRef. This
  82**   can be a reference to an existing or a newly created instruction.
  83**   Only the least-significant 16 bits (IRRef1) are used to form a TRef
  84**   which is finally returned to the caller.
  85**
  86** The FOLD engine receives instructions both from the trace recorder and
  87** substituted instructions from LOOP unrolling. This means all types
  88** of instructions may end up here, even though the recorder bypasses
  89** FOLD in some cases. Thus all loads, stores and allocations must have
  90** an any/any rule to avoid being passed on to CSE.
  91**
  92** Carefully read the following requirements before adding or modifying
  93** any fold rules:
  94**
  95** Requirement #1: All fold rules must preserve their destination type.
  96**
  97** Consistently use INTFOLD() (KINT result) or lj_ir_knum() (KNUM result).
  98** Never use lj_ir_knumint() which can have either a KINT or KNUM result.
  99**
 100** Requirement #2: Fold rules should not create *new* instructions which
 101** reference operands *across* PHIs.
 102**
 103** E.g. a RETRYFOLD with 'fins->op1 = fleft->op1' is invalid if the
 104** left operand is a PHI. Then fleft->op1 would point across the PHI
 105** frontier to an invariant instruction. Adding a PHI for this instruction
 106** would be counterproductive. The solution is to add a barrier which
 107** prevents folding across PHIs, i.e. 'PHIBARRIER(fleft)' in this case.
 108** The only exception is for recurrences with high latencies like
 109** repeated int->num->int conversions.
 110**
 111** One could relax this condition a bit if the referenced instruction is
 112** a PHI, too. But this often leads to worse code due to excessive
 113** register shuffling.
 114**
 115** Note: returning *existing* instructions (e.g. LEFTFOLD) is ok, though.
 116** Even returning fleft->op1 would be ok, because a new PHI will added,
 117** if needed. But again, this leads to excessive register shuffling and
 118** should be avoided.
 119**
 120** Requirement #3: The set of all fold rules must be monotonic to guarantee
 121** termination.
 122**
 123** The goal is optimization, so one primarily wants to add strength-reducing
 124** rules. This means eliminating an instruction or replacing an instruction
 125** with one or more simpler instructions. Don't add fold rules which point
 126** into the other direction.
 127**
 128** Some rules (like commutativity) do not directly reduce the strength of
 129** an instruction, but enable other fold rules (e.g. by moving constants
 130** to the right operand). These rules must be made unidirectional to avoid
 131** cycles.
 132**
 133** Rule of thumb: the trace recorder expands the IR and FOLD shrinks it.
 134*/
 135
 136/* Some local macros to save typing. Undef'd at the end. */
 137#define IR(ref)		(&J->cur.ir[(ref)])
 138#define fins		(&J->fold.ins)
 139#define fleft		(J->fold.left)
 140#define fright		(J->fold.right)
 141#define knumleft	(ir_knum(fleft)->n)
 142#define knumright	(ir_knum(fright)->n)
 143
 144/* Pass IR on to next optimization in chain (FOLD). */
 145#define emitir(ot, a, b)	(lj_ir_set(J, (ot), (a), (b)), lj_opt_fold(J))
 146
 147/* Fold function type. Fastcall on x86 significantly reduces their size. */
 148typedef IRRef (LJ_FASTCALL *FoldFunc)(jit_State *J);
 149
 150/* Macros for the fold specs, so buildvm can recognize them. */
 151#define LJFOLD(x)
 152#define LJFOLDX(x)
 153#define LJFOLDF(name)	static TRef LJ_FASTCALL fold_##name(jit_State *J)
 154/* Note: They must be at the start of a line or buildvm ignores them! */
 155
 156/* Barrier to prevent using operands across PHIs. */
 157#define PHIBARRIER(ir)	if (irt_isphi((ir)->t)) return NEXTFOLD
 158
 159/* Barrier to prevent folding across a GC step.
 160** GC steps can only happen at the head of a trace and at LOOP.
 161** And the GC is only driven forward if there's at least one allocation.
 162*/
 163#define gcstep_barrier(J, ref) \
 164  ((ref) < J->chain[IR_LOOP] && \
 165   (J->chain[IR_SNEW] || J->chain[IR_XSNEW] || \
 166    J->chain[IR_TNEW] || J->chain[IR_TDUP] || \
 167    J->chain[IR_CNEW] || J->chain[IR_CNEWI] || \
 168    J->chain[IR_BUFSTR] || J->chain[IR_TOSTR] || J->chain[IR_CALLA]))
 169
 170/* -- Constant folding for FP numbers ------------------------------------- */
 171
 172LJFOLD(ADD KNUM KNUM)
 173LJFOLD(SUB KNUM KNUM)
 174LJFOLD(MUL KNUM KNUM)
 175LJFOLD(DIV KNUM KNUM)
 176LJFOLD(LDEXP KNUM KNUM)
 177LJFOLD(MIN KNUM KNUM)
 178LJFOLD(MAX KNUM KNUM)
 179LJFOLDF(kfold_numarith)
 180{
 181  lua_Number a = knumleft;
 182  lua_Number b = knumright;
 183  lua_Number y = lj_vm_foldarith(a, b, fins->o - IR_ADD);
 184  return lj_ir_knum(J, y);
 185}
 186
 187LJFOLD(NEG KNUM FLOAD)
 188LJFOLD(ABS KNUM FLOAD)
 189LJFOLDF(kfold_numabsneg)
 190{
 191  lua_Number a = knumleft;
 192  lua_Number y = lj_vm_foldarith(a, a, fins->o - IR_ADD);
 193  return lj_ir_knum(J, y);
 194}
 195
 196LJFOLD(LDEXP KNUM KINT)
 197LJFOLDF(kfold_ldexp)
 198{
 199#if LJ_TARGET_X86ORX64
 200  UNUSED(J);
 201  return NEXTFOLD;
 202#else
 203  return lj_ir_knum(J, ldexp(knumleft, fright->i));
 204#endif
 205}
 206
 207LJFOLD(FPMATH KNUM any)
 208LJFOLDF(kfold_fpmath)
 209{
 210  lua_Number a = knumleft;
 211  lua_Number y = lj_vm_foldfpm(a, fins->op2);
 212  return lj_ir_knum(J, y);
 213}
 214
 215LJFOLD(CALLN KNUM any)
 216LJFOLDF(kfold_fpcall1)
 217{
 218  const CCallInfo *ci = &lj_ir_callinfo[fins->op2];
 219  if (CCI_TYPE(ci) == IRT_NUM) {
 220    double y = ((double (*)(double))ci->func)(knumleft);
 221    return lj_ir_knum(J, y);
 222  }
 223  return NEXTFOLD;
 224}
 225
 226LJFOLD(CALLN CARG IRCALL_atan2)
 227LJFOLDF(kfold_fpcall2)
 228{
 229  if (irref_isk(fleft->op1) && irref_isk(fleft->op2)) {
 230    const CCallInfo *ci = &lj_ir_callinfo[fins->op2];
 231    double a = ir_knum(IR(fleft->op1))->n;
 232    double b = ir_knum(IR(fleft->op2))->n;
 233    double y = ((double (*)(double, double))ci->func)(a, b);
 234    return lj_ir_knum(J, y);
 235  }
 236  return NEXTFOLD;
 237}
 238
 239LJFOLD(POW KNUM KNUM)
 240LJFOLDF(kfold_numpow)
 241{
 242  return lj_ir_knum(J, lj_vm_foldarith(knumleft, knumright, IR_POW - IR_ADD));
 243}
 244
 245/* Must not use kfold_kref for numbers (could be NaN). */
 246LJFOLD(EQ KNUM KNUM)
 247LJFOLD(NE KNUM KNUM)
 248LJFOLD(LT KNUM KNUM)
 249LJFOLD(GE KNUM KNUM)
 250LJFOLD(LE KNUM KNUM)
 251LJFOLD(GT KNUM KNUM)
 252LJFOLD(ULT KNUM KNUM)
 253LJFOLD(UGE KNUM KNUM)
 254LJFOLD(ULE KNUM KNUM)
 255LJFOLD(UGT KNUM KNUM)
 256LJFOLDF(kfold_numcomp)
 257{
 258  return CONDFOLD(lj_ir_numcmp(knumleft, knumright, (IROp)fins->o));
 259}
 260
 261/* -- Constant folding for 32 bit integers -------------------------------- */
 262
 263static int32_t kfold_intop(int32_t k1, int32_t k2, IROp op)
 264{
 265  switch (op) {
 266  case IR_ADD: k1 += k2; break;
 267  case IR_SUB: k1 -= k2; break;
 268  case IR_MUL: k1 *= k2; break;
 269  case IR_MOD: k1 = lj_vm_modi(k1, k2); break;
 270  case IR_NEG: k1 = (int32_t)(~(uint32_t)k1+1u); break;
 271  case IR_BAND: k1 &= k2; break;
 272  case IR_BOR: k1 |= k2; break;
 273  case IR_BXOR: k1 ^= k2; break;
 274  case IR_BSHL: k1 <<= (k2 & 31); break;
 275  case IR_BSHR: k1 = (int32_t)((uint32_t)k1 >> (k2 & 31)); break;
 276  case IR_BSAR: k1 >>= (k2 & 31); break;
 277  case IR_BROL: k1 = (int32_t)lj_rol((uint32_t)k1, (k2 & 31)); break;
 278  case IR_BROR: k1 = (int32_t)lj_ror((uint32_t)k1, (k2 & 31)); break;
 279  case IR_MIN: k1 = k1 < k2 ? k1 : k2; break;
 280  case IR_MAX: k1 = k1 > k2 ? k1 : k2; break;
 281  default: lj_assertX(0, "bad IR op %d", op); break;
 282  }
 283  return k1;
 284}
 285
 286LJFOLD(ADD KINT KINT)
 287LJFOLD(SUB KINT KINT)
 288LJFOLD(MUL KINT KINT)
 289LJFOLD(MOD KINT KINT)
 290LJFOLD(NEG KINT KINT)
 291LJFOLD(BAND KINT KINT)
 292LJFOLD(BOR KINT KINT)
 293LJFOLD(BXOR KINT KINT)
 294LJFOLD(BSHL KINT KINT)
 295LJFOLD(BSHR KINT KINT)
 296LJFOLD(BSAR KINT KINT)
 297LJFOLD(BROL KINT KINT)
 298LJFOLD(BROR KINT KINT)
 299LJFOLD(MIN KINT KINT)
 300LJFOLD(MAX KINT KINT)
 301LJFOLDF(kfold_intarith)
 302{
 303  return INTFOLD(kfold_intop(fleft->i, fright->i, (IROp)fins->o));
 304}
 305
 306/* Forward declaration. */
 307static uint64_t kfold_int64arith(jit_State *J, uint64_t k1, uint64_t k2,
 308				 IROp op);
 309
 310LJFOLD(ADDOV KINT KINT)
 311LJFOLD(SUBOV KINT KINT)
 312LJFOLD(MULOV KINT KINT)
 313LJFOLDF(kfold_intovarith)
 314{
 315  int64_t k = kfold_int64arith(J, (int64_t)fleft->i, (int64_t)fright->i,
 316		(IROp)((int)fins->o - (int)IR_ADDOV + (int)IR_ADD));
 317  return checki32(k) ? INTFOLD(k) : FAILFOLD;
 318}
 319
 320LJFOLD(BNOT KINT)
 321LJFOLDF(kfold_bnot)
 322{
 323  return INTFOLD(~fleft->i);
 324}
 325
 326LJFOLD(BSWAP KINT)
 327LJFOLDF(kfold_bswap)
 328{
 329  return INTFOLD((int32_t)lj_bswap((uint32_t)fleft->i));
 330}
 331
 332LJFOLD(LT KINT KINT)
 333LJFOLD(GE KINT KINT)
 334LJFOLD(LE KINT KINT)
 335LJFOLD(GT KINT KINT)
 336LJFOLD(ULT KINT KINT)
 337LJFOLD(UGE KINT KINT)
 338LJFOLD(ULE KINT KINT)
 339LJFOLD(UGT KINT KINT)
 340LJFOLD(ABC KINT KINT)
 341LJFOLDF(kfold_intcomp)
 342{
 343  int32_t a = fleft->i, b = fright->i;
 344  switch ((IROp)fins->o) {
 345  case IR_LT: return CONDFOLD(a < b);
 346  case IR_GE: return CONDFOLD(a >= b);
 347  case IR_LE: return CONDFOLD(a <= b);
 348  case IR_GT: return CONDFOLD(a > b);
 349  case IR_ULT: return CONDFOLD((uint32_t)a < (uint32_t)b);
 350  case IR_UGE: return CONDFOLD((uint32_t)a >= (uint32_t)b);
 351  case IR_ULE: return CONDFOLD((uint32_t)a <= (uint32_t)b);
 352  case IR_ABC:
 353  case IR_UGT: return CONDFOLD((uint32_t)a > (uint32_t)b);
 354  default: lj_assertJ(0, "bad IR op %d", fins->o); return FAILFOLD;
 355  }
 356}
 357
 358LJFOLD(UGE any KINT)
 359LJFOLDF(kfold_intcomp0)
 360{
 361  if (fright->i == 0)
 362    return DROPFOLD;
 363  return NEXTFOLD;
 364}
 365
 366/* -- Constant folding for 64 bit integers -------------------------------- */
 367
 368static uint64_t kfold_int64arith(jit_State *J, uint64_t k1, uint64_t k2,
 369				 IROp op)
 370{
 371  UNUSED(J);
 372  switch (op) {
 373  case IR_ADD: k1 += k2; break;
 374  case IR_SUB: k1 -= k2; break;
 375  case IR_MUL: k1 *= k2; break;
 376#if LJ_HASFFI
 377  case IR_BAND: k1 &= k2; break;
 378  case IR_BOR: k1 |= k2; break;
 379  case IR_BXOR: k1 ^= k2; break;
 380  case IR_BSHL: k1 <<= (k2 & 63); break;
 381  case IR_BSHR: k1 >>= (k2 & 63); break;
 382  case IR_BSAR: k1 = (uint64_t)((int64_t)k1 >> (k2 & 63)); break;
 383  case IR_BROL: k1 = lj_rol(k1, (k2 & 63)); break;
 384  case IR_BROR: k1 = lj_ror(k1, (k2 & 63)); break;
 385  default: lj_assertJ(0, "bad IR op %d", op); break;
 386#endif
 387  }
 388  return k1;
 389}
 390
 391LJFOLD(ADD KINT64 KINT64)
 392LJFOLD(SUB KINT64 KINT64)
 393LJFOLD(MUL KINT64 KINT64)
 394LJFOLD(BAND KINT64 KINT64)
 395LJFOLD(BOR KINT64 KINT64)
 396LJFOLD(BXOR KINT64 KINT64)
 397LJFOLDF(kfold_int64arith)
 398{
 399  return INT64FOLD(kfold_int64arith(J, ir_k64(fleft)->u64,
 400				    ir_k64(fright)->u64, (IROp)fins->o));
 401}
 402
 403LJFOLD(DIV KINT64 KINT64)
 404LJFOLD(MOD KINT64 KINT64)
 405LJFOLD(POW KINT64 KINT64)
 406LJFOLDF(kfold_int64arith2)
 407{
 408#if LJ_HASFFI
 409  uint64_t k1 = ir_k64(fleft)->u64, k2 = ir_k64(fright)->u64;
 410  if (irt_isi64(fins->t)) {
 411    k1 = fins->o == IR_DIV ? lj_carith_divi64((int64_t)k1, (int64_t)k2) :
 412	 fins->o == IR_MOD ? lj_carith_modi64((int64_t)k1, (int64_t)k2) :
 413			     lj_carith_powi64((int64_t)k1, (int64_t)k2);
 414  } else {
 415    k1 = fins->o == IR_DIV ? lj_carith_divu64(k1, k2) :
 416	 fins->o == IR_MOD ? lj_carith_modu64(k1, k2) :
 417			     lj_carith_powu64(k1, k2);
 418  }
 419  return INT64FOLD(k1);
 420#else
 421  UNUSED(J); lj_assertJ(0, "FFI IR op without FFI"); return FAILFOLD;
 422#endif
 423}
 424
 425LJFOLD(BSHL KINT64 KINT)
 426LJFOLD(BSHR KINT64 KINT)
 427LJFOLD(BSAR KINT64 KINT)
 428LJFOLD(BROL KINT64 KINT)
 429LJFOLD(BROR KINT64 KINT)
 430LJFOLDF(kfold_int64shift)
 431{
 432#if LJ_HASFFI
 433  uint64_t k = ir_k64(fleft)->u64;
 434  int32_t sh = (fright->i & 63);
 435  return INT64FOLD(lj_carith_shift64(k, sh, fins->o - IR_BSHL));
 436#else
 437  UNUSED(J); lj_assertJ(0, "FFI IR op without FFI"); return FAILFOLD;
 438#endif
 439}
 440
 441LJFOLD(BNOT KINT64)
 442LJFOLDF(kfold_bnot64)
 443{
 444#if LJ_HASFFI
 445  return INT64FOLD(~ir_k64(fleft)->u64);
 446#else
 447  UNUSED(J); lj_assertJ(0, "FFI IR op without FFI"); return FAILFOLD;
 448#endif
 449}
 450
 451LJFOLD(BSWAP KINT64)
 452LJFOLDF(kfold_bswap64)
 453{
 454#if LJ_HASFFI
 455  return INT64FOLD(lj_bswap64(ir_k64(fleft)->u64));
 456#else
 457  UNUSED(J); lj_assertJ(0, "FFI IR op without FFI"); return FAILFOLD;
 458#endif
 459}
 460
 461LJFOLD(LT KINT64 KINT64)
 462LJFOLD(GE KINT64 KINT64)
 463LJFOLD(LE KINT64 KINT64)
 464LJFOLD(GT KINT64 KINT64)
 465LJFOLD(ULT KINT64 KINT64)
 466LJFOLD(UGE KINT64 KINT64)
 467LJFOLD(ULE KINT64 KINT64)
 468LJFOLD(UGT KINT64 KINT64)
 469LJFOLDF(kfold_int64comp)
 470{
 471#if LJ_HASFFI
 472  uint64_t a = ir_k64(fleft)->u64, b = ir_k64(fright)->u64;
 473  switch ((IROp)fins->o) {
 474  case IR_LT: return CONDFOLD((int64_t)a < (int64_t)b);
 475  case IR_GE: return CONDFOLD((int64_t)a >= (int64_t)b);
 476  case IR_LE: return CONDFOLD((int64_t)a <= (int64_t)b);
 477  case IR_GT: return CONDFOLD((int64_t)a > (int64_t)b);
 478  case IR_ULT: return CONDFOLD(a < b);
 479  case IR_UGE: return CONDFOLD(a >= b);
 480  case IR_ULE: return CONDFOLD(a <= b);
 481  case IR_UGT: return CONDFOLD(a > b);
 482  default: lj_assertJ(0, "bad IR op %d", fins->o); return FAILFOLD;
 483  }
 484#else
 485  UNUSED(J); lj_assertJ(0, "FFI IR op without FFI"); return FAILFOLD;
 486#endif
 487}
 488
 489LJFOLD(UGE any KINT64)
 490LJFOLDF(kfold_int64comp0)
 491{
 492#if LJ_HASFFI
 493  if (ir_k64(fright)->u64 == 0)
 494    return DROPFOLD;
 495  return NEXTFOLD;
 496#else
 497  UNUSED(J); lj_assertJ(0, "FFI IR op without FFI"); return FAILFOLD;
 498#endif
 499}
 500
 501/* -- Constant folding for strings ---------------------------------------- */
 502
 503LJFOLD(SNEW KKPTR KINT)
 504LJFOLDF(kfold_snew_kptr)
 505{
 506  GCstr *s = lj_str_new(J->L, (const char *)ir_kptr(fleft), (size_t)fright->i);
 507  return lj_ir_kstr(J, s);
 508}
 509
 510LJFOLD(SNEW any KINT)
 511LJFOLD(XSNEW any KINT)
 512LJFOLDF(kfold_snew_empty)
 513{
 514  if (fright->i == 0)
 515    return lj_ir_kstr(J, &J2G(J)->strempty);
 516  return NEXTFOLD;
 517}
 518
 519LJFOLD(STRREF KGC KINT)
 520LJFOLDF(kfold_strref)
 521{
 522  GCstr *str = ir_kstr(fleft);
 523  lj_assertJ((MSize)fright->i <= str->len, "bad string ref");
 524  return lj_ir_kkptr(J, (char *)strdata(str) + fright->i);
 525}
 526
 527LJFOLD(STRREF SNEW any)
 528LJFOLDF(kfold_strref_snew)
 529{
 530  PHIBARRIER(fleft);
 531  if (irref_isk(fins->op2) && fright->i == 0) {
 532    return fleft->op1;  /* strref(snew(ptr, len), 0) ==> ptr */
 533  } else {
 534    /* Reassociate: strref(snew(strref(str, a), len), b) ==> strref(str, a+b) */
 535    IRIns *ir = IR(fleft->op1);
 536    if (ir->o == IR_STRREF) {
 537      IRRef1 str = ir->op1;  /* IRIns * is not valid across emitir. */
 538      PHIBARRIER(ir);
 539      fins->op2 = emitir(IRTI(IR_ADD), ir->op2, fins->op2); /* Clobbers fins! */
 540      fins->op1 = str;
 541      fins->ot = IRT(IR_STRREF, IRT_PGC);
 542      return RETRYFOLD;
 543    }
 544  }
 545  return NEXTFOLD;
 546}
 547
 548LJFOLD(CALLN CARG IRCALL_lj_str_cmp)
 549LJFOLDF(kfold_strcmp)
 550{
 551  if (irref_isk(fleft->op1) && irref_isk(fleft->op2)) {
 552    GCstr *a = ir_kstr(IR(fleft->op1));
 553    GCstr *b = ir_kstr(IR(fleft->op2));
 554    return INTFOLD(lj_str_cmp(a, b));
 555  }
 556  return NEXTFOLD;
 557}
 558
 559/* -- Constant folding and forwarding for buffers ------------------------- */
 560
 561/*
 562** Buffer ops perform stores, but their effect is limited to the buffer
 563** itself. Also, buffer ops are chained: a use of an op implies a use of
 564** all other ops up the chain. Conversely, if an op is unused, all ops
 565** up the chain can go unsed. This largely eliminates the need to treat
 566** them as stores.
 567**
 568** Alas, treating them as normal (IRM_N) ops doesn't work, because they
 569** cannot be CSEd in isolation. CSE for IRM_N is implicitly done in LOOP
 570** or if FOLD is disabled.
 571**
 572** The compromise is to declare them as loads, emit them like stores and
 573** CSE whole chains manually when the BUFSTR is to be emitted. Any chain
 574** fragments left over from CSE are eliminated by DCE.
 575**
 576** The string buffer methods emit a USE instead of a BUFSTR to keep the
 577** chain alive.
 578*/
 579
 580LJFOLD(BUFHDR any any)
 581LJFOLDF(bufhdr_merge)
 582{
 583  return fins->op2 == IRBUFHDR_WRITE ? CSEFOLD : EMITFOLD;
 584}
 585
 586LJFOLD(BUFPUT any BUFSTR)
 587LJFOLDF(bufput_bufstr)
 588{
 589  if ((J->flags & JIT_F_OPT_FWD)) {
 590    IRRef hdr = fright->op2;
 591    /* New buffer, no other buffer op inbetween and same buffer? */
 592    if (fleft->o == IR_BUFHDR && fleft->op2 == IRBUFHDR_RESET &&
 593	fleft->prev == hdr &&
 594	fleft->op1 == IR(hdr)->op1 &&
 595	!(irt_isphi(fright->t) && IR(hdr)->prev) &&
 596	(!LJ_HASBUFFER || J->chain[IR_CALLA] < hdr)) {
 597      IRRef ref = fins->op1;
 598      IR(ref)->op2 = IRBUFHDR_APPEND;  /* Modify BUFHDR. */
 599      IR(ref)->op1 = fright->op1;
 600      return ref;
 601    }
 602    /* Replay puts to global temporary buffer. */
 603    if (IR(hdr)->op2 == IRBUFHDR_RESET && !irt_isphi(fright->t)) {
 604      IRIns *ir = IR(fright->op1);
 605      /* For now only handle single string.reverse .lower .upper .rep. */
 606      if (ir->o == IR_CALLL &&
 607	  ir->op2 >= IRCALL_lj_buf_putstr_reverse &&
 608	  ir->op2 <= IRCALL_lj_buf_putstr_rep) {
 609	IRIns *carg1 = IR(ir->op1);
 610	if (ir->op2 == IRCALL_lj_buf_putstr_rep) {
 611	  IRIns *carg2 = IR(carg1->op1);
 612	  if (carg2->op1 == hdr) {
 613	    return lj_ir_call(J, ir->op2, fins->op1, carg2->op2, carg1->op2);
 614	  }
 615	} else if (carg1->op1 == hdr) {
 616	  return lj_ir_call(J, ir->op2, fins->op1, carg1->op2);
 617	}
 618      }
 619    }
 620  }
 621  return EMITFOLD;  /* Always emit, CSE later. */
 622}
 623
 624LJFOLD(BUFPUT any any)
 625LJFOLDF(bufput_kgc)
 626{
 627  if (LJ_LIKELY(J->flags & JIT_F_OPT_FOLD) && fright->o == IR_KGC) {
 628    GCstr *s2 = ir_kstr(fright);
 629    if (s2->len == 0) {  /* Empty string? */
 630      return LEFTFOLD;
 631    } else {
 632      if (fleft->o == IR_BUFPUT && irref_isk(fleft->op2) &&
 633	  !irt_isphi(fleft->t)) {  /* Join two constant string puts in a row. */
 634	GCstr *s1 = ir_kstr(IR(fleft->op2));
 635	IRRef kref = lj_ir_kstr(J, lj_buf_cat2str(J->L, s1, s2));
 636	/* lj_ir_kstr() may realloc the IR and invalidates any IRIns *. */
 637	IR(fins->op1)->op2 = kref;  /* Modify previous BUFPUT. */
 638	return fins->op1;
 639      }
 640    }
 641  }
 642  return EMITFOLD;  /* Always emit, CSE later. */
 643}
 644
 645LJFOLD(BUFSTR any any)
 646LJFOLDF(bufstr_kfold_cse)
 647{
 648  lj_assertJ(fleft->o == IR_BUFHDR || fleft->o == IR_BUFPUT ||
 649	     fleft->o == IR_CALLL,
 650	     "bad buffer constructor IR op %d", fleft->o);
 651  if (LJ_LIKELY(J->flags & JIT_F_OPT_FOLD)) {
 652    if (fleft->o == IR_BUFHDR) {  /* No put operations? */
 653      if (fleft->op2 == IRBUFHDR_RESET)  /* Empty buffer? */
 654	return lj_ir_kstr(J, &J2G(J)->strempty);
 655      fins->op1 = fleft->op1;
 656      fins->op2 = fleft->prev;  /* Relies on checks in bufput_append. */
 657      return CSEFOLD;
 658    } else if (fleft->o == IR_BUFPUT) {
 659      IRIns *irb = IR(fleft->op1);
 660      if (irb->o == IR_BUFHDR && irb->op2 == IRBUFHDR_RESET)
 661	return fleft->op2;  /* Shortcut for a single put operation. */
 662    }
 663  }
 664  /* Try to CSE the whole chain. */
 665  if (LJ_LIKELY(J->flags & JIT_F_OPT_CSE)) {
 666    IRRef ref = J->chain[IR_BUFSTR];
 667    while (ref) {
 668      IRIns *irs = IR(ref), *ira = fleft, *irb = IR(irs->op1);
 669      while (ira->o == irb->o && ira->op2 == irb->op2) {
 670	lj_assertJ(ira->o == IR_BUFHDR || ira->o == IR_BUFPUT ||
 671		   ira->o == IR_CALLL || ira->o == IR_CARG,
 672		   "bad buffer constructor IR op %d", ira->o);
 673	if (ira->o == IR_BUFHDR && ira->op2 == IRBUFHDR_RESET)
 674	  return ref;  /* CSE succeeded. */
 675	if (ira->o == IR_CALLL && ira->op2 == IRCALL_lj_buf_puttab)
 676	  break;
 677	ira = IR(ira->op1);
 678	irb = IR(irb->op1);
 679      }
 680      ref = irs->prev;
 681    }
 682  }
 683  return EMITFOLD;  /* No CSE possible. */
 684}
 685
 686LJFOLD(CALLL CARG IRCALL_lj_buf_putstr_reverse)
 687LJFOLD(CALLL CARG IRCALL_lj_buf_putstr_upper)
 688LJFOLD(CALLL CARG IRCALL_lj_buf_putstr_lower)
 689LJFOLD(CALLL CARG IRCALL_lj_strfmt_putquoted)
 690LJFOLDF(bufput_kfold_op)
 691{
 692  if (irref_isk(fleft->op2)) {
 693    const CCallInfo *ci = &lj_ir_callinfo[fins->op2];
 694    SBuf *sb = lj_buf_tmp_(J->L);
 695    sb = ((SBuf * (LJ_FASTCALL *)(SBuf *, GCstr *))ci->func)(sb,
 696						       ir_kstr(IR(fleft->op2)));
 697    fins->o = IR_BUFPUT;
 698    fins->op1 = fleft->op1;
 699    fins->op2 = lj_ir_kstr(J, lj_buf_tostr(sb));
 700    return RETRYFOLD;
 701  }
 702  return EMITFOLD;  /* Always emit, CSE later. */
 703}
 704
 705LJFOLD(CALLL CARG IRCALL_lj_buf_putstr_rep)
 706LJFOLDF(bufput_kfold_rep)
 707{
 708  if (irref_isk(fleft->op2)) {
 709    IRIns *irc = IR(fleft->op1);
 710    if (irref_isk(irc->op2)) {
 711      SBuf *sb = lj_buf_tmp_(J->L);
 712      sb = lj_buf_putstr_rep(sb, ir_kstr(IR(irc->op2)), IR(fleft->op2)->i);
 713      fins->o = IR_BUFPUT;
 714      fins->op1 = irc->op1;
 715      fins->op2 = lj_ir_kstr(J, lj_buf_tostr(sb));
 716      return RETRYFOLD;
 717    }
 718  }
 719  return EMITFOLD;  /* Always emit, CSE later. */
 720}
 721
 722LJFOLD(CALLL CARG IRCALL_lj_strfmt_putfxint)
 723LJFOLD(CALLL CARG IRCALL_lj_strfmt_putfnum_int)
 724LJFOLD(CALLL CARG IRCALL_lj_strfmt_putfnum_uint)
 725LJFOLD(CALLL CARG IRCALL_lj_strfmt_putfnum)
 726LJFOLD(CALLL CARG IRCALL_lj_strfmt_putfstr)
 727LJFOLD(CALLL CARG IRCALL_lj_strfmt_putfchar)
 728LJFOLDF(bufput_kfold_fmt)
 729{
 730  IRIns *irc = IR(fleft->op1);
 731  lj_assertJ(irref_isk(irc->op2), "SFormat must be const");
 732  if (irref_isk(fleft->op2)) {
 733    SFormat sf = (SFormat)IR(irc->op2)->i;
 734    IRIns *ira = IR(fleft->op2);
 735    SBuf *sb = lj_buf_tmp_(J->L);
 736    switch (fins->op2) {
 737    case IRCALL_lj_strfmt_putfxint:
 738      sb = lj_strfmt_putfxint(sb, sf, ir_k64(ira)->u64);
 739      break;
 740    case IRCALL_lj_strfmt_putfstr:
 741      sb = lj_strfmt_putfstr(sb, sf, ir_kstr(ira));
 742      break;
 743    case IRCALL_lj_strfmt_putfchar:
 744      sb = lj_strfmt_putfchar(sb, sf, ira->i);
 745      break;
 746    case IRCALL_lj_strfmt_putfnum_int:
 747    case IRCALL_lj_strfmt_putfnum_uint:
 748    case IRCALL_lj_strfmt_putfnum:
 749    default: {
 750      const CCallInfo *ci = &lj_ir_callinfo[fins->op2];
 751      sb = ((SBuf * (*)(SBuf *, SFormat, lua_Number))ci->func)(sb, sf,
 752							 ir_knum(ira)->n);
 753      break;
 754      }
 755    }
 756    fins->o = IR_BUFPUT;
 757    fins->op1 = irc->op1;
 758    fins->op2 = lj_ir_kstr(J, lj_buf_tostr(sb));
 759    return RETRYFOLD;
 760  }
 761  return EMITFOLD;  /* Always emit, CSE later. */
 762}
 763
 764/* -- Constant folding of pointer arithmetic ------------------------------ */
 765
 766LJFOLD(ADD KGC KINT)
 767LJFOLD(ADD KGC KINT64)
 768LJFOLDF(kfold_add_kgc)
 769{
 770  GCobj *o = ir_kgc(fleft);
 771#if LJ_64
 772  ptrdiff_t ofs = (ptrdiff_t)ir_kint64(fright)->u64;
 773#else
 774  ptrdiff_t ofs = fright->i;
 775#endif
 776#if LJ_HASFFI
 777  if (irt_iscdata(fleft->t)) {
 778    CType *ct = ctype_raw(ctype_ctsG(J2G(J)), gco2cd(o)->ctypeid);
 779    if (ctype_isnum(ct->info) || ctype_isenum(ct->info) ||
 780	ctype_isptr(ct->info) || ctype_isfunc(ct->info) ||
 781	ctype_iscomplex(ct->info) || ctype_isvector(ct->info))
 782      return lj_ir_kkptr(J, (char *)o + ofs);
 783  }
 784#endif
 785  return lj_ir_kptr(J, (char *)o + ofs);
 786}
 787
 788LJFOLD(ADD KPTR KINT)
 789LJFOLD(ADD KPTR KINT64)
 790LJFOLD(ADD KKPTR KINT)
 791LJFOLD(ADD KKPTR KINT64)
 792LJFOLDF(kfold_add_kptr)
 793{
 794  void *p = ir_kptr(fleft);
 795#if LJ_64
 796  ptrdiff_t ofs = (ptrdiff_t)ir_kint64(fright)->u64;
 797#else
 798  ptrdiff_t ofs = fright->i;
 799#endif
 800  return lj_ir_kptr_(J, fleft->o, (char *)p + ofs);
 801}
 802
 803LJFOLD(ADD any KGC)
 804LJFOLD(ADD any KPTR)
 805LJFOLD(ADD any KKPTR)
 806LJFOLDF(kfold_add_kright)
 807{
 808  if (fleft->o == IR_KINT || fleft->o == IR_KINT64) {
 809    IRRef1 tmp = fins->op1; fins->op1 = fins->op2; fins->op2 = tmp;
 810    return RETRYFOLD;
 811  }
 812  return NEXTFOLD;
 813}
 814
 815/* -- Constant folding of conversions ------------------------------------- */
 816
 817LJFOLD(TOBIT KNUM KNUM)
 818LJFOLDF(kfold_tobit)
 819{
 820  return INTFOLD(lj_num2bit(knumleft));
 821}
 822
 823LJFOLD(CONV KINT IRCONV_NUM_INT)
 824LJFOLDF(kfold_conv_kint_num)
 825{
 826  return lj_ir_knum(J, (lua_Number)fleft->i);
 827}
 828
 829LJFOLD(CONV KINT IRCONV_NUM_U32)
 830LJFOLDF(kfold_conv_kintu32_num)
 831{
 832  return lj_ir_knum(J, (lua_Number)(uint32_t)fleft->i);
 833}
 834
 835LJFOLD(CONV KINT IRCONV_INT_I8)
 836LJFOLD(CONV KINT IRCONV_INT_U8)
 837LJFOLD(CONV KINT IRCONV_INT_I16)
 838LJFOLD(CONV KINT IRCONV_INT_U16)
 839LJFOLDF(kfold_conv_kint_ext)
 840{
 841  int32_t k = fleft->i;
 842  if ((fins->op2 & IRCONV_SRCMASK) == IRT_I8) k = (int8_t)k;
 843  else if ((fins->op2 & IRCONV_SRCMASK) == IRT_U8) k = (uint8_t)k;
 844  else if ((fins->op2 & IRCONV_SRCMASK) == IRT_I16) k = (int16_t)k;
 845  else k = (uint16_t)k;
 846  return INTFOLD(k);
 847}
 848
 849LJFOLD(CONV KINT IRCONV_I64_INT)
 850LJFOLD(CONV KINT IRCONV_U64_INT)
 851LJFOLD(CONV KINT IRCONV_I64_U32)
 852LJFOLD(CONV KINT IRCONV_U64_U32)
 853LJFOLDF(kfold_conv_kint_i64)
 854{
 855  if ((fins->op2 & IRCONV_SEXT))
 856    return INT64FOLD((uint64_t)(int64_t)fleft->i);
 857  else
 858    return INT64FOLD((uint64_t)(int64_t)(uint32_t)fleft->i);
 859}
 860
 861LJFOLD(CONV KINT64 IRCONV_NUM_I64)
 862LJFOLDF(kfold_conv_kint64_num_i64)
 863{
 864  return lj_ir_knum(J, (lua_Number)(int64_t)ir_kint64(fleft)->u64);
 865}
 866
 867LJFOLD(CONV KINT64 IRCONV_NUM_U64)
 868LJFOLDF(kfold_conv_kint64_num_u64)
 869{
 870  return lj_ir_knum(J, (lua_Number)ir_kint64(fleft)->u64);
 871}
 872
 873LJFOLD(CONV KINT64 IRCONV_INT_I64)
 874LJFOLD(CONV KINT64 IRCONV_U32_I64)
 875LJFOLDF(kfold_conv_kint64_int_i64)
 876{
 877  return INTFOLD((int32_t)ir_kint64(fleft)->u64);
 878}
 879
 880LJFOLD(CONV KNUM IRCONV_INT_NUM)
 881LJFOLDF(kfold_conv_knum_int_num)
 882{
 883  lua_Number n = knumleft;
 884  if (irt_isguard(fins->t)) {
 885    int64_t i64;
 886    int32_t k;
 887    if (lj_num2int_check(n, i64, k))
 888      return INTFOLD(k);
 889    /* We're about to create a guard which always fails, like CONV +1.5.
 890    ** Some pathological loops cause this during LICM, e.g.:
 891    **   local x,k,t = 0,1.5,{1,[1.5]=2}
 892    **   for i=1,200 do x = x+ t[k]; k = k == 1 and 1.5 or 1 end
 893    **   assert(x == 300)
 894    */
 895    return FAILFOLD;
 896  } else {
 897    return INTFOLD(lj_num2int(n));
 898  }
 899}
 900
 901LJFOLD(CONV KNUM IRCONV_I64_NUM)
 902LJFOLDF(kfold_conv_knum_i64_num)
 903{
 904  return INT64FOLD((uint64_t)lj_num2i64(knumleft));
 905}
 906
 907LJFOLD(CONV KNUM IRCONV_U64_NUM)
 908LJFOLDF(kfold_conv_knum_u64_num)
 909{
 910  return INT64FOLD(lj_num2u64(knumleft));
 911}
 912
 913LJFOLD(TOSTR KNUM any)
 914LJFOLDF(kfold_tostr_knum)
 915{
 916  return lj_ir_kstr(J, lj_strfmt_num(J->L, ir_knum(fleft)));
 917}
 918
 919LJFOLD(TOSTR KINT any)
 920LJFOLDF(kfold_tostr_kint)
 921{
 922  return lj_ir_kstr(J, fins->op2 == IRTOSTR_INT ?
 923		       lj_strfmt_int(J->L, fleft->i) :
 924		       lj_strfmt_char(J->L, fleft->i));
 925}
 926
 927LJFOLD(STRTO KGC)
 928LJFOLDF(kfold_strto)
 929{
 930  TValue n;
 931  if (lj_strscan_num(ir_kstr(fleft), &n))
 932    return lj_ir_knum(J, numV(&n));
 933  return FAILFOLD;
 934}
 935
 936/* -- Constant folding of equality checks --------------------------------- */
 937
 938/* Don't constant-fold away FLOAD checks against KNULL. */
 939LJFOLD(EQ FLOAD KNULL)
 940LJFOLD(NE FLOAD KNULL)
 941LJFOLDX(lj_opt_cse)
 942
 943/* But fold all other KNULL compares, since only KNULL is equal to KNULL. */
 944LJFOLD(EQ any KNULL)
 945LJFOLD(NE any KNULL)
 946LJFOLD(EQ KNULL any)
 947LJFOLD(NE KNULL any)
 948LJFOLD(EQ KINT KINT)  /* Constants are unique, so same refs <==> same value. */
 949LJFOLD(NE KINT KINT)
 950LJFOLD(EQ KINT64 KINT64)
 951LJFOLD(NE KINT64 KINT64)
 952LJFOLD(EQ KGC KGC)
 953LJFOLD(NE KGC KGC)
 954LJFOLDF(kfold_kref)
 955{
 956  return CONDFOLD((fins->op1 == fins->op2) ^ (fins->o == IR_NE));
 957}
 958
 959/* -- Algebraic shortcuts ------------------------------------------------- */
 960
 961LJFOLD(FPMATH FPMATH IRFPM_FLOOR)
 962LJFOLD(FPMATH FPMATH IRFPM_CEIL)
 963LJFOLD(FPMATH FPMATH IRFPM_TRUNC)
 964LJFOLDF(shortcut_round)
 965{
 966  IRFPMathOp op = (IRFPMathOp)fleft->op2;
 967  if (op == IRFPM_FLOOR || op == IRFPM_CEIL || op == IRFPM_TRUNC)
 968    return LEFTFOLD;  /* round(round_left(x)) = round_left(x) */
 969  return NEXTFOLD;
 970}
 971
 972LJFOLD(ABS ABS FLOAD)
 973LJFOLDF(shortcut_left)
 974{
 975  return LEFTFOLD;  /* f(g(x)) ==> g(x) */
 976}
 977
 978LJFOLD(ABS NEG FLOAD)
 979LJFOLDF(shortcut_dropleft)
 980{
 981  PHIBARRIER(fleft);
 982  fins->op1 = fleft->op1;  /* abs(neg(x)) ==> abs(x) */
 983  return RETRYFOLD;
 984}
 985
 986/* Note: no safe shortcuts with STRTO and TOSTR ("1e2" ==> +100 ==> "100"). */
 987LJFOLD(NEG NEG any)
 988LJFOLD(BNOT BNOT)
 989LJFOLD(BSWAP BSWAP)
 990LJFOLDF(shortcut_leftleft)
 991{
 992  PHIBARRIER(fleft);  /* See above. Fold would be ok, but not beneficial. */
 993  return fleft->op1;  /* f(g(x)) ==> x */
 994}
 995
 996/* -- FP algebraic simplifications ---------------------------------------- */
 997
 998/* FP arithmetic is tricky -- there's not much to simplify.
 999** Please note the following common pitfalls before sending "improvements":
1000**   x+0 ==> x  is INVALID for x=-0
1001**   0-x ==> -x is INVALID for x=+0
1002**   x*0 ==> 0  is INVALID for x=-0, x=+-Inf or x=NaN
1003*/
1004
1005LJFOLD(ADD NEG any)
1006LJFOLDF(simplify_numadd_negx)
1007{
1008  PHIBARRIER(fleft);
1009  fins->o = IR_SUB;  /* (-a) + b ==> b - a */
1010  fins->op1 = fins->op2;
1011  fins->op2 = fleft->op1;
1012  return RETRYFOLD;
1013}
1014
1015LJFOLD(ADD any NEG)
1016LJFOLDF(simplify_numadd_xneg)
1017{
1018  PHIBARRIER(fright);
1019  fins->o = IR_SUB;  /* a + (-b) ==> a - b */
1020  fins->op2 = fright->op1;
1021  return RETRYFOLD;
1022}
1023
1024LJFOLD(SUB any KNUM)
1025LJFOLDF(simplify_numsub_k)
1026{
1027  if (ir_knum(fright)->u64 == 0)  /* x - (+0) ==> x */
1028    return LEFTFOLD;
1029  return NEXTFOLD;
1030}
1031
1032LJFOLD(SUB NEG KNUM)
1033LJFOLDF(simplify_numsub_negk)
1034{
1035  PHIBARRIER(fleft);
1036  fins->op2 = fleft->op1;  /* (-x) - k ==> (-k) - x */
1037  fins->op1 = (IRRef1)lj_ir_knum(J, -knumright);
1038  return RETRYFOLD;
1039}
1040
1041LJFOLD(SUB any NEG)
1042LJFOLDF(simplify_numsub_xneg)
1043{
1044  PHIBARRIER(fright);
1045  fins->o = IR_ADD;  /* a - (-b) ==> a + b */
1046  fins->op2 = fright->op1;
1047  return RETRYFOLD;
1048}
1049
1050LJFOLD(MUL any KNUM)
1051LJFOLD(DIV any KNUM)
1052LJFOLDF(simplify_nummuldiv_k)
1053{
1054  lua_Number n = knumright;
1055  if (n == 1.0) {  /* x o 1 ==> x */
1056    return LEFTFOLD;
1057  } else if (n == -1.0) {  /* x o -1 ==> -x */
1058    IRRef op1 = fins->op1;
1059    fins->op2 = (IRRef1)lj_ir_ksimd(J, LJ_KSIMD_NEG);  /* Modifies fins. */
1060    fins->op1 = op1;
1061    fins->o = IR_NEG;
1062    return RETRYFOLD;
1063  } else if (fins->o == IR_MUL && n == 2.0) {  /* x * 2 ==> x + x */
1064    fins->o = IR_ADD;
1065    fins->op2 = fins->op1;
1066    return RETRYFOLD;
1067  } else if (fins->o == IR_DIV) {  /* x / 2^k ==> x * 2^-k */
1068    uint64_t u = ir_knum(fright)->u64;
1069    uint32_t ex = ((uint32_t)(u >> 52) & 0x7ff);
1070    if ((u & U64x(000fffff,ffffffff)) == 0 && ex - 1 < 0x7fd) {
1071      u = (u & ((uint64_t)1 << 63)) | ((uint64_t)(0x7fe - ex) << 52);
1072      fins->o = IR_MUL;  /* Multiply by exact reciprocal. */
1073      fins->op2 = lj_ir_knum_u64(J, u);
1074      return RETRYFOLD;
1075    }
1076  }
1077  return NEXTFOLD;
1078}
1079
1080LJFOLD(MUL NEG KNUM)
1081LJFOLD(DIV NEG KNUM)
1082LJFOLDF(simplify_nummuldiv_negk)
1083{
1084  PHIBARRIER(fleft);
1085  fins->op1 = fleft->op1;  /* (-a) o k ==> a o (-k) */
1086  fins->op2 = (IRRef1)lj_ir_knum(J, -knumright);
1087  return RETRYFOLD;
1088}
1089
1090LJFOLD(MUL NEG NEG)
1091LJFOLD(DIV NEG NEG)
1092LJFOLDF(simplify_nummuldiv_negneg)
1093{
1094  PHIBARRIER(fleft);
1095  PHIBARRIER(fright);
1096  fins->op1 = fleft->op1;  /* (-a) o (-b) ==> a o b */
1097  fins->op2 = fright->op1;
1098  return RETRYFOLD;
1099}
1100
1101LJFOLD(POW any KNUM)
1102LJFOLDF(simplify_numpow_k)
1103{
1104  if (knumright == 0.0)  /* x ^ 0 ==> 1 */
1105    return lj_ir_knum_one(J);  /* Result must be a number, not an int. */
1106  else if (knumright == 1.0)  /* x ^ 1 ==> x */
1107    return LEFTFOLD;
1108  else if (knumright == 2.0)  /* x ^ 2 ==> x * x */
1109    return emitir(IRTN(IR_MUL), fins->op1, fins->op1);
1110  else
1111    return NEXTFOLD;
1112}
1113
1114/* -- Simplify conversions ------------------------------------------------ */
1115
1116LJFOLD(CONV CONV IRCONV_NUM_INT)  /* _NUM */
1117LJFOLDF(shortcut_conv_num_int)
1118{
1119  PHIBARRIER(fleft);
1120  /* Only safe with a guarded conversion to int. */
1121  if ((fleft->op2 & IRCONV_SRCMASK) == IRT_NUM && irt_isguard(fleft->t))
1122    return fleft->op1;  /* f(g(x)) ==> x */
1123  return NEXTFOLD;
1124}
1125
1126LJFOLD(CONV CONV IRCONV_INT_NUM)  /* _INT */
1127LJFOLDF(simplify_conv_int_num)
1128{
1129  /* Fold even across PHI to avoid expensive num->int conversions in loop. */
1130  if ((fleft->op2 & IRCONV_SRCMASK) ==
1131      ((fins->op2 & IRCONV_DSTMASK) >> IRCONV_DSH))
1132    return fleft->op1;
1133  return NEXTFOLD;
1134}
1135
1136LJFOLD(CONV CONV IRCONV_I64_NUM)  /* _INT or _U32 */
1137LJFOLD(CONV CONV IRCONV_U64_NUM)  /* _INT or _U32 */
1138LJFOLDF(simplify_conv_i64_num)
1139{
1140  PHIBARRIER(fleft);
1141  if ((fleft->op2 & IRCONV_SRCMASK) == IRT_INT) {
1142    /* Reduce to a sign-extension. */
1143    fins->op1 = fleft->op1;
1144    fins->op2 = ((IRT_I64<<5)|IRT_INT|IRCONV_SEXT);
1145    return RETRYFOLD;
1146  } else if ((fleft->op2 & IRCONV_SRCMASK) == IRT_U32) {
1147#if LJ_TARGET_X64
1148    return fleft->op1;
1149#else
1150    /* Reduce to a zero-extension. */
1151    fins->op1 = fleft->op1;
1152    fins->op2 = (IRT_I64<<5)|IRT_U32;
1153    return RETRYFOLD;
1154#endif
1155  }
1156  return NEXTFOLD;
1157}
1158
1159LJFOLD(CONV CONV IRCONV_INT_I64)  /* _INT or _U32 */
1160LJFOLD(CONV CONV IRCONV_INT_U64)  /* _INT or _U32 */
1161LJFOLD(CONV CONV IRCONV_INT_U32)  /* _INT or _U32 */
1162LJFOLD(CONV CONV IRCONV_U32_I64)  /* _INT or _U32 */
1163LJFOLD(CONV CONV IRCONV_U32_U64)  /* _INT or _U32 */
1164LJFOLD(CONV CONV IRCONV_U32_INT)  /* _INT or _U32 */
1165LJFOLDF(simplify_conv_int_i64)
1166{
1167  int src;
1168  PHIBARRIER(fleft);
1169  src = (fleft->op2 & IRCONV_SRCMASK);
1170  if (src == IRT_INT || src == IRT_U32) {
1171    if (src == ((fins->op2 & IRCONV_DSTMASK) >> IRCONV_DSH)) {
1172      return fleft->op1;
1173    } else {
1174      fins->op2 = ((fins->op2 & IRCONV_DSTMASK) | src);
1175      fins->op1 = fleft->op1;
1176      return RETRYFOLD;
1177    }
1178  }
1179  return NEXTFOLD;
1180}
1181
1182LJFOLD(CONV CONV IRCONV_FLOAT_NUM)  /* _FLOAT */
1183LJFOLDF(simplify_conv_flt_num)
1184{
1185  PHIBARRIER(fleft);
1186  if ((fleft->op2 & IRCONV_SRCMASK) == IRT_FLOAT)
1187    return fleft->op1;
1188  return NEXTFOLD;
1189}
1190
1191/* Shortcut TOBIT + IRT_NUM <- IRT_INT/IRT_U32 conversion. */
1192LJFOLD(TOBIT CONV KNUM)
1193LJFOLDF(simplify_tobit_conv)
1194{
1195  /* Fold even across PHI to avoid expensive num->int conversions in loop. */
1196  if ((fleft->op2 & IRCONV_SRCMASK) == IRT_INT) {
1197    lj_assertJ(irt_isnum(fleft->t), "expected TOBIT number arg");
1198    return fleft->op1;
1199  } else if ((fleft->op2 & IRCONV_SRCMASK) == IRT_U32) {
1200    lj_assertJ(irt_isnum(fleft->t), "expected TOBIT number arg");
1201    fins->o = IR_CONV;
1202    fins->op1 = fleft->op1;
1203    fins->op2 = (IRT_INT<<5)|IRT_U32;
1204    return RETRYFOLD;
1205  }
1206  return NEXTFOLD;
1207}
1208
1209/* Shortcut floor/ceil/trunc + IRT_NUM <- integer conversion. */
1210LJFOLD(FPMATH CONV IRFPM_FLOOR)
1211LJFOLD(FPMATH CONV IRFPM_CEIL)
1212LJFOLD(FPMATH CONV IRFPM_TRUNC)
1213LJFOLDF(simplify_floor_conv)
1214{
1215  if ((uint32_t)(fleft->op2 & IRCONV_SRCMASK) - (uint32_t)IRT_I8 <= (uint32_t)(IRT_U64 - IRT_U8))
1216    return LEFTFOLD;
1217  return NEXTFOLD;
1218}
1219
1220/* Strength reduction of widening. */
1221LJFOLD(CONV any IRCONV_I64_INT)
1222LJFOLD(CONV any IRCONV_U64_INT)
1223LJFOLDF(simplify_conv_sext)
1224{
1225  IRRef ref = fins->op1;
1226  int64_t ofs = 0;
1227  if (!(fins->op2 & IRCONV_SEXT))
1228    return NEXTFOLD;
1229  PHIBARRIER(fleft);
1230  if (fleft->o == IR_XLOAD && (irt_isu8(fleft->t) || irt_isu16(fleft->t)))
1231    goto ok_reduce;
1232  if (fleft->o == IR_ADD && irref_isk(fleft->op2)) {
1233    ofs = (int64_t)IR(fleft->op2)->i;
1234    ref = fleft->op1;
1235  }
1236  /* Use scalar evolution analysis results to strength-reduce sign-extension. */
1237  if (ref == J->scev.idx) {
1238    IRRef lo = J->scev.dir ? J->scev.start : J->scev.stop;
1239    lj_assertJ(irt_isint(J->scev.t), "only int SCEV supported");
1240    if (lo && IR(lo)->o == IR_KINT && IR(lo)->i + ofs >= 0) {
1241    ok_reduce:
1242#if LJ_TARGET_X64
1243      /* Eliminate widening. All 32 bit ops do an implicit zero-extension. */
1244      return LEFTFOLD;
1245#else
1246      /* Reduce to a (cheaper) zero-extension. */
1247      fins->op2 &= ~IRCONV_SEXT;
1248      return RETRYFOLD;
1249#endif
1250    }
1251  }
1252  return NEXTFOLD;
1253}
1254
1255/* Strength reduction of narrowing. */
1256LJFOLD(CONV ADD IRCONV_INT_I64)
1257LJFOLD(CONV SUB IRCONV_INT_I64)
1258LJFOLD(CONV MUL IRCONV_INT_I64)
1259LJFOLD(CONV ADD IRCONV_INT_U64)
1260LJFOLD(CONV SUB IRCONV_INT_U64)
1261LJFOLD(CONV MUL IRCONV_INT_U64)
1262LJFOLD(CONV ADD IRCONV_U32_I64)
1263LJFOLD(CONV SUB IRCONV_U32_I64)
1264LJFOLD(CONV MUL IRCONV_U32_I64)
1265LJFOLD(CONV ADD IRCONV_U32_U64)
1266LJFOLD(CONV SUB IRCONV_U32_U64)
1267LJFOLD(CONV MUL IRCONV_U32_U64)
1268LJFOLDF(simplify_conv_narrow)
1269{
1270#if LJ_64
1271  UNUSED(J);
1272  return NEXTFOLD;
1273#else
1274  IROp op = (IROp)fleft->o;
1275  IRType t = irt_type(fins->t);
1276  IRRef op1 = fleft->op1, op2 = fleft->op2, mode = fins->op2;
1277  PHIBARRIER(fleft);
1278  op1 = emitir(IRT(IR_CONV, t), op1, mode);
1279  op2 = emitir(IRT(IR_CONV, t), op2, mode);
1280  fins->ot = IRT(op, t);
1281  fins->op1 = op1;
1282  fins->op2 = op2;
1283  return RETRYFOLD;
1284#endif
1285}
1286
1287/* Special CSE rule for CONV. */
1288LJFOLD(CONV any any)
1289LJFOLDF(cse_conv)
1290{
1291  if (LJ_LIKELY(J->flags & JIT_F_OPT_CSE)) {
1292    IRRef op1 = fins->op1, op2 = (fins->op2 & IRCONV_MODEMASK);
1293    uint8_t guard = irt_isguard(fins->t);
1294    IRRef ref = J->chain[IR_CONV];
1295    while (ref > op1) {
1296      IRIns *ir = IR(ref);
1297      /* Commoning with stronger checks is ok. */
1298      if (ir->op1 == op1 && (ir->op2 & IRCONV_MODEMASK) == op2 &&
1299	  irt_isguard(ir->t) >= guard)
1300	return ref;
1301      ref = ir->prev;
1302    }
1303  }
1304  return EMITFOLD;  /* No fallthrough to regular CSE. */
1305}
1306
1307/* FP conversion narrowing. */
1308LJFOLD(TOBIT ADD KNUM)
1309LJFOLD(TOBIT SUB KNUM)
1310LJFOLD(CONV ADD IRCONV_INT_NUM)
1311LJFOLD(CONV SUB IRCONV_INT_NUM)
1312LJFOLD(CONV ADD IRCONV_I64_NUM)
1313LJFOLD(CONV SUB IRCONV_I64_NUM)
1314LJFOLDF(narrow_convert)
1315{
1316  PHIBARRIER(fleft);
1317  /* Narrowing ignores PHIs and repeating it inside the loop is not useful. */
1318  if (J->chain[IR_LOOP])
1319    return NEXTFOLD;
1320  lj_assertJ(fins->o != IR_CONV || (fins->op2&IRCONV_CONVMASK) != IRCONV_TOBIT,
1321	     "unexpected CONV TOBIT");
1322  return lj_opt_narrow_convert(J);
1323}
1324
1325LJFOLD(XSTORE any CONV)
1326LJFOLDF(xstore_conv)
1327{
1328#if LJ_64
1329  PHIBARRIER(fright);
1330  if (!irt_is64(fins->t) &&
1331      irt_type(fins->t) == (IRType)((fright->op2&IRCONV_DSTMASK)>>IRCONV_DSH) &&
1332      ((fright->op2&IRCONV_SRCMASK) == IRT_I64 ||
1333       (fright->op2&IRCONV_SRCMASK) == IRT_U64)) {
1334    fins->op2 = fright->op1;
1335    return RETRYFOLD;
1336  }
1337#else
1338  UNUSED(J);
1339#endif
1340  return NEXTFOLD;
1341}
1342
1343/* -- Integer algebraic simplifications ----------------------------------- */
1344
1345LJFOLD(ADD any KINT)
1346LJFOLD(ADDOV any KINT)
1347LJFOLD(SUBOV any KINT)
1348LJFOLDF(simplify_intadd_k)
1349{
1350  if (fright->i == 0)  /* i o 0 ==> i */
1351    return LEFTFOLD;
1352  return NEXTFOLD;
1353}
1354
1355LJFOLD(MULOV any KINT)
1356LJFOLDF(simplify_intmul_k)
1357{
1358  if (fright->i == 0)  /* i * 0 ==> 0 */
1359    return RIGHTFOLD;
1360  if (fright->i == 1)  /* i * 1 ==> i */
1361    return LEFTFOLD;
1362  if (fright->i == 2) {  /* i * 2 ==> i + i */
1363    fins->o = IR_ADDOV;
1364    fins->op2 = fins->op1;
1365    return RETRYFOLD;
1366  }
1367  return NEXTFOLD;
1368}
1369
1370LJFOLD(SUB any KINT)
1371LJFOLDF(simplify_intsub_k)
1372{
1373  if (fright->i == 0)  /* i - 0 ==> i */
1374    return LEFTFOLD;
1375  fins->o = IR_ADD;  /* i - k ==> i + (-k) */
1376  fins->op2 = (IRRef1)lj_ir_kint(J, (int32_t)(~(uint32_t)fright->i+1u));  /* Overflow for -2^31 ok. */
1377  return RETRYFOLD;
1378}
1379
1380LJFOLD(SUB KINT any)
1381LJFOLD(SUB KINT64 any)
1382LJFOLDF(simplify_intsub_kleft)
1383{
1384  if (fleft->o == IR_KINT ? (fleft->i == 0) : (ir_kint64(fleft)->u64 == 0)) {
1385    fins->o = IR_NEG;  /* 0 - i ==> -i */
1386    fins->op1 = fins->op2;
1387    return RETRYFOLD;
1388  }
1389  return NEXTFOLD;
1390}
1391
1392LJFOLD(ADD any KINT64)
1393LJFOLDF(simplify_intadd_k64)
1394{
1395  if (ir_kint64(fright)->u64 == 0)  /* i + 0 ==> i */
1396    return LEFTFOLD;
1397  return NEXTFOLD;
1398}
1399
1400LJFOLD(SUB any KINT64)
1401LJFOLDF(simplify_intsub_k64)
1402{
1403  uint64_t k = ir_kint64(fright)->u64;
1404  if (k == 0)  /* i - 0 ==> i */
1405    return LEFTFOLD;
1406  fins->o = IR_ADD;  /* i - k ==> i + (-k) */
1407  fins->op2 = (IRRef1)lj_ir_kint64(J, ~k+1u);
1408  return RETRYFOLD;
1409}
1410
1411static TRef simplify_intmul_k(jit_State *J, int32_t k)
1412{
1413  /* Note: many more simplifications are possible, e.g. 2^k1 +- 2^k2.
1414  ** But this is mainly intended for simple address arithmetic.
1415  ** Also it's easier for the backend to optimize the original multiplies.
1416  */
1417  if (k == 0) {  /* i * 0 ==> 0 */
1418    return RIGHTFOLD;
1419  } else if (k == 1) {  /* i * 1 ==> i */
1420    return LEFTFOLD;
1421  } else if ((k & (k-1)) == 0) {  /* i * 2^k ==> i << k */
1422    fins->o = IR_BSHL;
1423    fins->op2 = lj_ir_kint(J, lj_fls((uint32_t)k));
1424    return RETRYFOLD;
1425  }
1426  return NEXTFOLD;
1427}
1428
1429LJFOLD(MUL any KINT)
1430LJFOLDF(simplify_intmul_k32)
1431{
1432  if (fright->i >= 0)
1433    return simplify_intmul_k(J, fright->i);
1434  return NEXTFOLD;
1435}
1436
1437LJFOLD(MUL any KINT64)
1438LJFOLDF(simplify_intmul_k64)
1439{
1440#if LJ_HASFFI
1441  if (ir_kint64(fright)->u64 < 0x80000000u)
1442    return simplify_intmul_k(J, (int32_t)ir_kint64(fright)->u64);
1443  return NEXTFOLD;
1444#else
1445  UNUSED(J); lj_assertJ(0, "FFI IR op without FFI"); return FAILFOLD;
1446#endif
1447}
1448
1449LJFOLD(MOD any KINT)
1450LJFOLDF(simplify_intmod_k)
1451{
1452  int32_t k = fright->i;
1453  lj_assertJ(k != 0, "integer mod 0");
1454  if (k > 0 && (k & (k-1)) == 0) {  /* i % (2^k) ==> i & (2^k-1) */
1455    fins->o = IR_BAND;
1456    fins->op2 = lj_ir_kint(J, k-1);
1457    return RETRYFOLD;
1458  }
1459  return NEXTFOLD;
1460}
1461
1462LJFOLD(MOD KINT any)
1463LJFOLDF(simplify_intmod_kleft)
1464{
1465  if (fleft->i == 0)
1466    return INTFOLD(0);
1467  return NEXTFOLD;
1468}
1469
1470LJFOLD(SUB any any)
1471LJFOLD(SUBOV any any)
1472LJFOLDF(simplify_intsub)
1473{
1474  if (fins->op1 == fins->op2 && !irt_isnum(fins->t))  /* i - i ==> 0 */
1475    return irt_is64(fins->t) ? INT64FOLD(0) : INTFOLD(0);
1476  return NEXTFOLD;
1477}
1478
1479LJFOLD(SUB ADD any)
1480LJFOLDF(simplify_intsubadd_leftcancel)
1481{
1482  if (!irt_isnum(fins->t)) {
1483    PHIBARRIER(fleft);
1484    if (fins->op2 == fleft->op1)  /* (i + j) - i ==> j */
1485      return fleft->op2;
1486    if (fins->op2 == fleft->op2)  /* (i + j) - j ==> i */
1487      return fleft->op1;
1488  }
1489  return NEXTFOLD;
1490}
1491
1492LJFOLD(SUB SUB any)
1493LJFOLDF(simplify_intsubsub_leftcancel)
1494{
1495  if (!irt_isnum(fins->t)) {
1496    PHIBARRIER(fleft);
1497    if (fins->op2 == fleft->op1) {  /* (i - j) - i ==> 0 - j */
1498      fins->op1 = (IRRef1)lj_ir_kint(J, 0);
1499      fins->op2 = fleft->op2;
1500      return RETRYFOLD;
1501    }
1502  }
1503  return NEXTFOLD;
1504}
1505
1506LJFOLD(SUB any SUB)
1507LJFOLDF(simplify_intsubsub_rightcancel)
1508{
1509  if (!irt_isnum(fins->t)) {
1510    PHIBARRIER(fright);
1511    if (fins->op1 == fright->op1)  /* i - (i - j) ==> j */
1512      return fright->op2;
1513  }
1514  return NEXTFOLD;
1515}
1516
1517LJFOLD(SUB any ADD)
1518LJFOLDF(simplify_intsubadd_rightcancel)
1519{
1520  if (!irt_isnum(fins->t)) {
1521    PHIBARRIER(fright);
1522    if (fins->op1 == fright->op1) {  /* i - (i + j) ==> 0 - j */
1523      fins->op2 = fright->op2;
1524      fins->op1 = (IRRef1)lj_ir_kint(J, 0);
1525      return RETRYFOLD;
1526    }
1527    if (fins->op1 == fright->op2) {  /* i - (j + i) ==> 0 - j */
1528      fins->op2 = fright->op1;
1529      fins->op1 = (IRRef1)lj_ir_kint(J, 0);
1530      return RETRYFOLD;
1531    }
1532  }
1533  return NEXTFOLD;
1534}
1535
1536LJFOLD(SUB ADD ADD)
1537LJFOLDF(simplify_intsubaddadd_cancel)
1538{
1539  if (!irt_isnum(fins->t)) {
1540    PHIBARRIER(fleft);
1541    PHIBARRIER(fright);
1542    if (fleft->op1 == fright->op1) {  /* (i + j1) - (i + j2) ==> j1 - j2 */
1543      fins->op1 = fleft->op2;
1544      fins->op2 = fright->op2;
1545      return RETRYFOLD;
1546    }
1547    if (fleft->op1 == fright->op2) {  /* (i + j1) - (j2 + i) ==> j1 - j2 */
1548      fins->op1 = fleft->op2;
1549      fins->op2 = fright->op1;
1550      return RETRYFOLD;
1551    }
1552    if (fleft->op2 == fright->op1) {  /* (j1 + i) - (i + j2) ==> j1 - j2 */
1553      fins->op1 = fleft->op1;
1554      fins->op2 = fright->op2;
1555      return RETRYFOLD;
1556    }
1557    if (fleft->op2 == fright->op2) {  /* (j1 + i) - (j2 + i) ==> j1 - j2 */
1558      fins->op1 = fleft->op1;
1559      fins->op2 = fright->op1;
1560      return RETRYFOLD;
1561    }
1562  }
1563  return NEXTFOLD;
1564}
1565
1566LJFOLD(BAND any KINT)
1567LJFOLD(BAND any KINT64)
1568LJFOLDF(simplify_band_k)
1569{
1570  int64_t k = fright->o == IR_KINT ? (int64_t)fright->i :
1571				     (int64_t)ir_k64(fright)->u64;
1572  if (k == 0)  /* i & 0 ==> 0 */
1573    return RIGHTFOLD;
1574  if (k == -1)  /* i & -1 ==> i */
1575    return LEFTFOLD;
1576  return NEXTFOLD;
1577}
1578
1579LJFOLD(BOR any KINT)
1580LJFOLD(BOR any KINT64)
1581LJFOLDF(simplify_bor_k)
1582{
1583  int64_t k = fright->o == IR_KINT ? (int64_t)fright->i :
1584				     (int64_t)ir_k64(fright)->u64;
1585  if (k == 0)  /* i | 0 ==> i */
1586    return LEFTFOLD;
1587  if (k == -1)  /* i | -1 ==> -1 */
1588    return RIGHTFOLD;
1589  return NEXTFOLD;
1590}
1591
1592LJFOLD(BXOR any KINT)
1593LJFOLD(BXOR any KINT64)
1594LJFOLDF(simplify_bxor_k)
1595{
1596  int64_t k = fright->o == IR_KINT ? (int64_t)fright->i :
1597				     (int64_t)ir_k64(fright)->u64;
1598  if (k == 0)  /* i xor 0 ==> i */
1599    return LEFTFOLD;
1600  if (k == -1) {  /* i xor -1 ==> ~i */
1601    fins->o = IR_BNOT;
1602    fins->op2 = 0;
1603    return RETRYFOLD;
1604  }
1605  return NEXTFOLD;
1606}
1607
1608LJFOLD(BSHL any KINT)
1609LJFOLD(BSHR any KINT)
1610LJFOLD(BSAR any KINT)
1611LJFOLD(BROL any KINT)
1612LJFOLD(BROR any KINT)
1613LJFOLDF(simplify_shift_ik)
1614{
1615  int32_t mask = irt_is64(fins->t) ? 63 : 31;
1616  int32_t k = (fright->i & mask);
1617  if (k == 0)  /* i o 0 ==> i */
1618    return LEFTFOLD;
1619  if (k == 1 && fins->o == IR_BSHL) {  /* i << 1 ==> i + i */
1620    fins->o = IR_ADD;
1621    fins->op2 = fins->op1;
1622    return RETRYFOLD;
1623  }
1624  if (k != fright->i) {  /* i o k ==> i o (k & mask) */
1625    fins->op2 = (IRRef1)lj_ir_kint(J, k);
1626    return RETRYFOLD;
1627  }
1628#ifndef LJ_TARGET_UNIFYROT
1629  if (fins->o == IR_BROR) {  /* bror(i, k) ==> brol(i, (-k)&mask) */
1630    fins->o = IR_BROL;
1631    fins->op2 = (IRRef1)lj_ir_kint(J, (-k)&mask);
1632    return RETRYFOLD;
1633  }
1634#endif
1635  return NEXTFOLD;
1636}
1637
1638LJFOLD(BSHL any BAND)
1639LJFOLD(BSHR any BAND)
1640LJFOLD(BSAR any BAND)
1641LJFOLD(BROL any BAND)
1642LJFOLD(BROR any BAND)
1643LJFOLDF(simplify_shift_andk)
1644{
1645  IRIns *irk = IR(fright->op2);
1646  PHIBARRIER(fright);
1647  if ((fins->o < IR_BROL ? LJ_TARGET_MASKSHIFT : LJ_TARGET_MASKROT) &&
1648      irk->o == IR_KINT) {  /* i o (j & mask) ==> i o j */
1649    int32_t mask = irt_is64(fins->t) ? 63 : 31;
1650    int32_t k = irk->i & mask;
1651    if (k == mask) {
1652      fins->op2 = fright->op1;
1653      return RETRYFOLD;
1654    }
1655  }
1656  return NEXTFOLD;
1657}
1658
1659LJFOLD(BSHL KINT any)
1660LJFOLD(BSHR KINT any)
1661LJFOLD(BSHL KINT64 any)
1662LJFOLD(BSHR KINT64 any)
1663LJFOLDF(simplify_shift1_ki)
1664{
1665  int64_t k = fleft->o == IR_KINT ? (int64_t)fleft->i :
1666				    (int64_t)ir_k64(fleft)->u64;
1667  if (k == 0)  /* 0 o i ==> 0 */
1668    return LEFTFOLD;
1669  return NEXTFOLD;
1670}
1671
1672LJFOLD(BSAR KINT any)
1673LJFOLD(BROL KINT any)
1674LJFOLD(BROR KINT any)
1675LJFOLD(BSAR KINT64 any)
1676LJFOLD(BROL KINT64 any)
1677LJFOLD(BROR KINT64 any)
1678LJFOLDF(simplify_shift2_ki)
1679{
1680  int64_t k = fleft->o == IR_KINT ? (int64_t)fleft->i :
1681				    (int64_t)ir_k64(fleft)->u64;
1682  if (k == 0 || k == -1)  /* 0 o i ==> 0; -1 o i ==> -1 */
1683    return LEFTFOLD;
1684  return NEXTFOLD;
1685}
1686
1687LJFOLD(BSHL BAND KINT)
1688LJFOLD(BSHR BAND KINT)
1689LJFOLD(BROL BAND KINT)
1690LJFOLD(BROR BAND KINT)
1691LJFOLDF(simplify_shiftk_andk)
1692{
1693  IRIns *irk = IR(fleft->op2);
1694  PHIBARRIER(fleft);
1695  if (irk->o == IR_KINT) {  /* (i & k1) o k2 ==> (i o k2) & (k1 o k2) */
1696    int32_t k = kfold_intop(irk->i, fright->i, (IROp)fins->o);
1697    fins->op1 = fleft->op1;
1698    fins->op1 = (IRRef1)lj_opt_fold(J);
1699    fins->op2 = (IRRef1)lj_ir_kint(J, k);
1700    fins->ot = IRTI(IR_BAND);
1701    return RETRYFOLD;
1702  } else if (irk->o == IR_KINT64) {
1703    uint64_t k = kfold_int64arith(J, ir_k64(irk)->u64, fright->i,
1704				  (IROp)fins->o);
1705    IROpT ot = fleft->ot;
1706    fins->op1 = fleft->op1;
1707    fins->op1 = (IRRef1)lj_opt_fold(J);
1708    fins->op2 = (IRRef1)lj_ir_kint64(J, k);
1709    fins->ot = ot;
1710    return RETRYFOLD;
1711  }
1712  return NEXTFOLD;
1713}
1714
1715LJFOLD(BAND BSHL KINT)
1716LJFOLD(BAND BSHR KINT)
1717LJFOLDF(simplify_andk_shiftk)
1718{
1719  IRIns *irk = IR(fleft->op2);
1720  if (irk->o == IR_KINT &&
1721      kfold_intop(-1, irk->i, (IROp)fleft->o) == fright->i)
1722    return LEFTFOLD;  /* (i o k1) & k2 ==> i, if (-1 o k1) == k2 */
1723  return NEXTFOLD;
1724}
1725
1726LJFOLD(BAND BOR KINT)
1727LJFOLD(BOR BAND KINT)
1728LJFOLDF(simplify_andor_k)
1729{
1730  IRIns *irk = IR(fleft->op2);
1731  PHIBARRIER(fleft);
1732  if (irk->o == IR_KINT) {
1733    int32_t k = kfold_intop(irk->i, fright->i, (IROp)fins->o);
1734    /* (i | k1) & k2 ==> i & k2, if (k1 & k2) == 0. */
1735    /* (i & k1) | k2 ==> i | k2, if (k1 | k2) == -1. */
1736    if (k == (fins->o == IR_BAND ? 0 : -1)) {
1737      fins->op1 = fleft->op1;
1738      return RETRYFOLD;
1739    }
1740  }
1741  return NEXTFOLD;
1742}
1743
1744LJFOLD(BAND BOR KINT64)
1745LJFOLD(BOR BAND KINT64)
1746LJFOLDF(simplify_andor_k64)
1747{
1748#if LJ_HASFFI
1749  IRIns *irk = IR(fleft->op2);
1750  PHIBARRIER(fleft);
1751  if (irk->o == IR_KINT64) {
1752    uint64_t k = kfold_int64arith(J, ir_k64(irk)->u64, ir_k64(fright)->u64,
1753				  (IROp)fins->o);
1754    /* (i | k1) & k2 ==> i & k2, if (k1 & k2) == 0. */
1755    /* (i & k1) | k2 ==> i | k2, if (k1 | k2) == -1. */
1756    if (k == (fins->o == IR_BAND ? (uint64_t)0 : ~(uint64_t)0)) {
1757      fins->op1 = fleft->op1;
1758      return RETRYFOLD;
1759    }
1760  }
1761  return NEXTFOLD;
1762#else
1763  UNUSED(J); lj_assertJ(0, "FFI IR op without FFI"); return FAILFOLD;
1764#endif
1765}
1766
1767/* -- Reassociation ------------------------------------------------------- */
1768
1769LJFOLD(ADD ADD KINT)
1770LJFOLD(MUL MUL KINT)
1771LJFOLD(BAND BAND KINT)
1772LJFOLD(BOR BOR KINT)
1773LJFOLD(BXOR BXOR KINT)
1774LJFOLDF(reassoc_intarith_k)
1775{
1776  IRIns *irk = IR(fleft->op2);
1777  if (irk->o == IR_KINT) {
1778    int32_t k = kfold_intop(irk->i, fright->i, (IROp)fins->o);
1779    if (k == irk->i)  /* (i o k1) o k2 ==> i o k1, if (k1 o k2) == k1. */
1780      return LEFTFOLD;
1781    PHIBARRIER(fleft);
1782    fins->op1 = fleft->op1;
1783    fins->op2 = (IRRef1)lj_ir_kint(J, k);
1784    return RETRYFOLD;  /* (i o k1) o k2 ==> i o (k1 o k2) */
1785  }
1786  return NEXTFOLD;
1787}
1788
1789LJFOLD(ADD ADD KINT64)
1790LJFOLD(MUL MUL KINT64)
1791LJFOLD(BAND BAND KINT64)
1792LJFOLD(BOR BOR KINT64)
1793LJFOLD(BXOR BXOR KINT64)
1794LJFOLDF(reassoc_intarith_k64)
1795{
1796#if LJ_HASFFI
1797  IRIns *irk = IR(fleft->op2);
1798  if (irk->o == IR_KINT64) {
1799    uint64_t k = kfold_int64arith(J, ir_k64(irk)->u64, ir_k64(fright)->u64,
1800				  (IROp)fins->o);
1801    PHIBARRIER(fleft);
1802    fins->op1 = fleft->op1;
1803    fins->op2 = (IRRef1)lj_ir_kint64(J, k);
1804    return RETRYFOLD;  /* (i o k1) o k2 ==> i o (k1 o k2) */
1805  }
1806  return NEXTFOLD;
1807#else
1808  UNUSED(J); lj_assertJ(0, "FFI IR op without FFI"); return FAILFOLD;
1809#endif
1810}
1811
1812LJFOLD(BAND BAND any)
1813LJFOLD(BOR BOR any)
1814LJFOLDF(reassoc_dup)
1815{
1816  if (fins->op2 == fleft->op1 || fins->op2 == fleft->op2)
1817    return LEFTFOLD;  /* (a o b) o a ==> a o b; (a o b) o b ==> a o b */
1818  return NEXTFOLD;
1819}
1820
1821LJFOLD(MIN MIN any)
1822LJFOLD(MAX MAX any)
1823LJFOLDF(reassoc_dup_minmax)
1824{
1825  if (fins->op2 == fleft->op2)
1826    return LEFTFOLD;  /* (a o b) o b ==> a o b */
1827  return NEXTFOLD;
1828}
1829
1830LJFOLD(BXOR BXOR any)
1831LJFOLDF(reassoc_bxor)
1832{
1833  PHIBARRIER(fleft);
1834  if (fins->op2 == fleft->op1)  /* (a xor b) xor a ==> b */
1835    return fleft->op2;
1836  if (fins->op2 == fleft->op2)  /* (a xor b) xor b ==> a */
1837    return fleft->op1;
1838  return NEXTFOLD;
1839}
1840
1841LJFOLD(BSHL BSHL KINT)
1842LJFOLD(BSHR BSHR KINT)
1843LJFOLD(BSAR BSAR KINT)
1844LJFOLD(BROL BROL KINT)
1845LJFOLD(BROR BROR KINT)
1846LJFOLDF(reassoc_shift)
1847{
1848  IRIns *irk = IR(fleft->op2);
1849  PHIBARRIER(fleft);  /* The (shift any KINT) rule covers k2 == 0 and more. */
1850  if (irk->o == IR_KINT) {  /* (i o k1) o k2 ==> i o (k1 + k2) */
1851    int32_t mask = irt_is64(fins->t) ? 63 : 31;
1852    int32_t k = (irk->i & mask) + (fright->i & mask);
1853    if (k > mask) {  /* Combined shift too wide? */
1854      if (fins->o == IR_BSHL || fins->o == IR_BSHR)
1855	return mask == 31 ? INTFOLD(0) : INT64FOLD(0);
1856      else if (fins->o == IR_BSAR)
1857	k = mask;
1858      else
1859	k &= mask;
1860    }
1861    fins->op1 = fleft->op1;
1862    fins->op2 = (IRRef1)lj_ir_kint(J, k);
1863    return RETRYFOLD;
1864  }
1865  return NEXTFOLD;
1866}
1867
1868LJFOLD(MIN MIN KINT)
1869LJFOLD(MAX MAX KINT)
1870LJFOLDF(reassoc_minmax_k)
1871{
1872  IRIns *irk = IR(fleft->op2);
1873  if (irk->o == IR_KINT) {
1874    int32_t a = irk->i;
1875    int32_t y = kfold_intop(a, fright->i, fins->o);
1876    if (a == y)  /* (x o k1) o k2 ==> x o k1, if (k1 o k2) == k1. */
1877      return LEFTFOLD;
1878    PHIBARRIER(fleft);
1879    fins->op1 = fleft->op1;
1880    fins->op2 = (IRRef1)lj_ir_kint(J, y);
1881    return RETRYFOLD;  /* (x o k1) o k2 ==> x o (k1 o k2) */
1882  }
1883  return NEXTFOLD;
1884}
1885
1886/* -- Array bounds check elimination -------------------------------------- */
1887
1888/* Eliminate ABC across PHIs to handle t[i-1] forwarding case.
1889** ABC(asize, (i+k)+(-k)) ==> ABC(asize, i), but only if it already exists.
1890** Could be generalized to (i+k1)+k2 ==> i+(k1+k2), but needs better disambig.
1891*/
1892LJFOLD(ABC any ADD)
1893LJFOLDF(abc_fwd)
1894{
1895  if (LJ_LIKELY(J->flags & JIT_F_OPT_ABC)) {
1896    if (irref_isk(fright->op2)) {
1897      IRIns *add2 = IR(fright->op1);
1898      if (add2->o == IR_ADD && irref_isk(add2->op2) &&
1899	  IR(fright->op2)->i == -IR(add2->op2)->i) {
1900	IRRef ref = J->chain[IR_ABC];
1901	IRRef lim = add2->op1;
1902	if (fins->op1 > lim) lim = fins->op1;
1903	while (ref > lim) {
1904	  IRIns *ir = IR(ref);
1905	  if (ir->op1 == fins->op1 && ir->op2 == add2->op1)
1906	    return DROPFOLD;
1907	  ref = ir->prev;
1908	}
1909      }
1910    }
1911  }
1912  return NEXTFOLD;
1913}
1914
1915/* Eliminate ABC for constants.
1916** ABC(asize, k1), ABC(asize k2) ==> ABC(asize, max(k1, k2))
1917** Drop second ABC if k2 is lower. Otherwise patch first ABC with k2.
1918*/
1919LJFOLD(ABC any KINT)
1920LJFOLDF(abc_k)
1921{
1922  PHIBARRIER(fleft);
1923  if (LJ_LIKELY(J->flags & JIT_F_OPT_ABC)) {
1924    IRRef ref = J->chain[IR_ABC];
1925    IRRef asize = fins->op1;
1926    while (ref > asize) {
1927      IRIns *ir = IR(ref);
1928      if (ir->op1 == asize && irref_isk(ir->op2)) {
1929	uint32_t k = (uint32_t)IR(ir->op2)->i;
1930	if ((uint32_t)fright->i > k)
1931	  ir->op2 = fins->op2;
1932	return DROPFOLD;
1933      }
1934      ref = ir->prev;
1935    }
1936    return EMITFOLD;  /* Already performed CSE. */
1937  }
1938  return NEXTFOLD;
1939}
1940
1941/* Eliminate invariant ABC inside loop. */
1942LJFOLD(ABC any any)
1943LJFOLDF(abc_invar)
1944{
1945  /* Invariant ABC marked as P32 or U32. Drop if op1 is invariant too. */
1946  if (!irt_isint(fins->t) && fins->op1 < J->chain[IR_LOOP] &&
1947      (irt_isu32(fins->t) ||
1948       (!irref_isk(fins->op1) && !irt_isphi(IR(fins->op1)->t))))
1949    return DROPFOLD;
1950  return NEXTFOLD;
1951}
1952
1953/* -- Commutativity ------------------------------------------------------- */
1954
1955/* The refs of commutative ops are canonicalized. Lower refs go to the right.
1956** Rationale behind this:
1957** - It (also) moves constants to the right.
1958** - It reduces the number of FOLD rules (e.g. (BOR any KINT) suffices).
1959** - It helps CSE to find more matches.
1960** - The assembler generates better code with constants at the right.
1961*/
1962
1963LJFOLD(ADD any any)
1964LJFOLD(MUL any any)
1965LJFOLD(ADDOV any any)
1966LJFOLD(MULOV any any)
1967LJFOLDF(comm_swap)
1968{
1969  if (fins->op1 < fins->op2) {  /* Move lower ref to the right. */
1970    IRRef1 tmp = fins->op1;
1971    fins->op1 = fins->op2;
1972    fins->op2 = tmp;
1973    return RETRYFOLD;
1974  }
1975  return NEXTFOLD;
1976}
1977
1978LJFOLD(EQ any any)
1979LJFOLD(NE any any)
1980LJFOLDF(comm_equal)
1981{
1982  /* For non-numbers only: x == x ==> drop; x ~= x ==> fail */
1983  if (fins->op1 == fins->op2 &&
1984      (!irt_isnum(fins->t) ||
1985       (fleft->o == IR_CONV &&  /* Converted integers cannot be NaN. */
1986	(uint32_t)(fleft->op2 & IRCONV_SRCMASK) - (uint32_t)IRT_I8 <= (uint32_t)(IRT_U64 - IRT_U8))))
1987    return CONDFOLD(fins->o == IR_EQ);
1988  return fold_comm_swap(J);
1989}
1990
1991LJFOLD(LT any any)
1992LJFOLD(GE any any)
1993LJFOLD(LE any any)
1994LJFOLD(GT any any)
1995LJFOLD(ULT any any)
1996LJFOLD(UGE any any)
1997LJFOLD(ULE any any)
1998LJFOLD(UGT any any)
1999LJFOLDF(comm_comp)
2000{
2001  /* For non-numbers only: x <=> x ==> drop; x <> x ==> fail */
2002  if (fins->op1 == fins->op2 && !irt_isnum(fins->t))
2003    return CONDFOLD((fins->o ^ (fins->o >> 1)) & 1);
2004  if (fins->op1 < fins->op2) {  /* Move lower ref to the right. */
2005    IRRef1 tmp = fins->op1;
2006    fins->op1 = fins->op2;
2007    fins->op2 = tmp;
2008    fins->o ^= 3; /* GT <-> LT, GE <-> LE, does not affect U */
2009    return RETRYFOLD;
2010  }
2011  return NEXTFOLD;
2012}
2013
2014LJFOLD(BAND any any)
2015LJFOLD(BOR any any)
2016LJFOLDF(comm_dup)
2017{
2018  if (fins->op1 == fins->op2)  /* x o x ==> x */
2019    return LEFTFOLD;
2020  return fold_comm_swap(J);
2021}
2022
2023LJFOLD(MIN any any)
2024LJFOLD(MAX any any)
2025LJFOLDF(comm_dup_minmax)
2026{
2027  if (fins->op1 == fins->op2)  /* x o x ==> x */
2028    return LEFTFOLD;
2029  return NEXTFOLD;
2030}
2031
2032LJFOLD(BXOR any any)
2033LJFOLDF(comm_bxor)
2034{
2035  if (fins->op1 == fins->op2)  /* i xor i ==> 0 */
2036    return irt_is64(fins->t) ? INT64FOLD(0) : INTFOLD(0);
2037  return fold_comm_swap(J);
2038}
2039
2040/* -- Simplification of compound expressions ------------------------------ */
2041
2042static TRef kfold_xload(jit_State *J, IRIns *ir, const void *p)
2043{
2044  int32_t k;
2045  switch (irt_type(ir->t)) {
2046  case IRT_NUM: return lj_ir_knum_u64(J, *(uint64_t *)p);
2047  case IRT_I8: k = (int32_t)*(int8_t *)p; break;
2048  case IRT_U8: k = (int32_t)*(uint8_t *)p; break;
2049  case IRT_I16: k = (int32_t)(int16_t)lj_getu16(p); break;
2050  case IRT_U16: k = (int32_t)(uint16_t)lj_getu16(p); break;
2051  case IRT_INT: case IRT_U32: k = (int32_t)lj_getu32(p); break;
2052  case IRT_I64: case IRT_U64: return lj_ir_kint64(J, *(uint64_t *)p);
2053  default: return 0;
2054  }
2055  return lj_ir_kint(J, k);
2056}
2057
2058/* Turn: string.sub(str, a, b) == kstr
2059** into: string.byte(str, a) == string.byte(kstr, 1) etc.
2060** Note: this creates unaligned XLOADs on x86/x64.
2061*/
2062LJFOLD(EQ SNEW KGC)
2063LJFOLD(NE SNEW KGC)
2064LJFOLDF(merge_eqne_snew_kgc)
2065{
2066  GCstr *kstr = ir_kstr(fright);
2067  int32_t len = (int32_t)kstr->len;
2068  lj_assertJ(irt_isstr(fins->t), "bad equality IR type");
2069
2070#if LJ_TARGET_UNALIGNED
2071#define FOLD_SNEW_MAX_LEN	4  /* Handle string lengths 0, 1, 2, 3, 4. */
2072#define FOLD_SNEW_TYPE8		IRT_I8	/* Creates shorter immediates. */
2073#else
2074#define FOLD_SNEW_MAX_LEN	1  /* Handle string lengths 0 or 1. */
2075#define FOLD_SNEW_TYPE8		IRT_U8  /* Prefer unsigned loads. */
2076#endif
2077
2078  PHIBARRIER(fleft);
2079  if (len <= FOLD_SNEW_MAX_LEN) {
2080    IROp op = (IROp)fins->o;
2081    IRRef strref = fleft->op1;
2082    if (IR(strref)->o != IR_STRREF)
2083      return NEXTFOLD;
2084    if (op == IR_EQ) {
2085      emitir(IRTGI(IR_EQ), fleft->op2, lj_ir_kint(J, len));
2086      /* Caveat: fins/fleft/fright is no longer valid after emitir. */
2087    } else {
2088      /* NE is not expanded since this would need an OR of two conds. */
2089      if (!irref_isk(fleft->op2))  /* Only handle the constant length case. */
2090	return NEXTFOLD;
2091      if (IR(fleft->op2)->i != len)
2092	return DROPFOLD;
2093    }
2094    if (len > 0) {
2095      /* A 4 byte load for length 3 is ok -- all strings have an extra NUL. */
2096      uint16_t ot = (uint16_t)(len == 1 ? IRT(IR_XLOAD, FOLD_SNEW_TYPE8) :
2097			       len == 2 ? IRT(IR_XLOAD, IRT_U16) :
2098			       IRTI(IR_XLOAD));
2099      TRef tmp = emitir(ot, strref,
2100			IRXLOAD_READONLY | (len > 1 ? IRXLOAD_UNALIGNED : 0));
2101      TRef val = kfold_xload(J, IR(tref_ref(tmp)), strdata(kstr));
2102      if (len == 3)
2103	tmp = emitir(IRTI(IR_BAND), tmp,
2104		     lj_ir_kint(J, LJ_ENDIAN_SELECT(0x00ffffff, 0xffffff00)));
2105      fins->op1 = (IRRef1)tmp;
2106      fins->op2 = (IRRef1)val;
2107      fins->ot = (IROpT)IRTGI(op);
2108      return RETRYFOLD;
2109    } else {
2110      return DROPFOLD;
2111    }
2112  }
2113  return NEXTFOLD;
2114}
2115
2116/* -- Loads --------------------------------------------------------------- */
2117
2118/* Loads cannot be folded or passed on to CSE in general.
2119** Alias analysis is needed to check for forwarding opportunities.
2120**
2121** Caveat: *all* loads must be listed here or they end up at CSE!
2122*/
2123
2124LJFOLD(ALOAD any)
2125LJFOLDX(lj_opt_fwd_aload)
2126
2127/* From HREF fwd (see below). Must eliminate, not supported by fwd/backend. */
2128LJFOLD(HLOAD KKPTR)
2129LJFOLDF(kfold_hload_kkptr)
2130{
2131  UNUSED(J);
2132  lj_assertJ(ir_kptr(fleft) == niltvg(J2G(J)), "expected niltv");
2133  return TREF_NIL;
2134}
2135
2136LJFOLD(HLOAD any)
2137LJFOLDX(lj_opt_fwd_hload)
2138
2139LJFOLD(ULOAD any)
2140LJFOLDX(lj_opt_fwd_uload)
2141
2142LJFOLD(ALEN any any)
2143LJFOLDX(lj_opt_fwd_alen)
2144
2145/* Try to merge UREFO/UREFC into referenced instruction. */
2146static TRef merge_uref(jit_State *J, IRRef ref, IRIns* ir)
2147{
2148  if (ir->o == IR_UREFO && irt_isguard(ir->t)) {
2149    /* Might be pointing to some other coroutine's stack.
2150    ** And GC might shrink said stack, thereby repointing the upvalue.
2151    ** GC might even collect said coroutine, thereby closing the upvalue.
2152    */
2153    if (gcstep_barrier(J, ref))
2154      return EMITFOLD;  /* So cannot merge. */
2155    /* Current fins wants a check, but ir doesn't have one. */
2156    if ((irt_t(fins->t) & (IRT_GUARD|IRT_TYPE)) == (IRT_GUARD|IRT_PGC) &&
2157	irt_type(ir->t) == IRT_IGC)
2158      ir->t.irt += IRT_PGC-IRT_IGC;  /* So install a check. */
2159  }
2160  return ref;  /* Not a TRef, but the caller doesn't care. */
2161}
2162
2163/* Upvalue refs are really loads, but there are no corresponding stores.
2164** So CSE is ok for them, except for guarded UREFO across a GC step.
2165** If the referenced function is const, its upvalue addresses are const, too.
2166** This can be used to improve CSE by looking for the same address,
2167** even if the upvalues originate from a different function.
2168*/
2169LJFOLD(UREFO KGC any)
2170LJFOLD(UREFC KGC any)
2171LJFOLDF(cse_uref)
2172{
2173  if (LJ_LIKELY(J->flags & JIT_F_OPT_CSE)) {
2174    IRRef ref = J->chain[fins->o];
2175    GCfunc *fn = ir_kfunc(fleft);
2176    GCupval *uv = gco2uv(gcref(fn->l.uvptr[(fins->op2 >> 8)]));
2177    while (ref > 0) {
2178      IRIns *ir = IR(ref);
2179      if (irref_isk(ir->op1)) {
2180	GCfunc *fn2 = ir_kfunc(IR(ir->op1));
2181	if (gco2uv(gcref(fn2->l.uvptr[(ir->op2 >> 8)])) == uv) {
2182	  return merge_uref(J, ref, ir);
2183	}
2184      }
2185      ref = ir->prev;
2186    }
2187  }
2188  return EMITFOLD;
2189}
2190
2191/* Custom CSE for UREFO. */
2192LJFOLD(UREFO any any)
2193LJFOLDF(cse_urefo)
2194{
2195  if (LJ_LIKELY(J->flags & JIT_F_OPT_CSE)) {
2196    IRRef ref = J->chain[IR_UREFO];
2197    IRRef lim = fins->op1;
2198    IRRef2 op12 = (IRRef2)fins->op1 + ((IRRef2)fins->op2 << 16);
2199    while (ref > lim) {
2200      IRIns *ir = IR(ref);
2201      if (ir->op12 == op12)
2202	return merge_uref(J, ref, ir);
2203      ref = ir->prev;
2204    }
2205  }
2206  return EMITFOLD;
2207}
2208
2209LJFOLD(HREFK any any)
2210LJFOLDX(lj_opt_fwd_hrefk)
2211
2212LJFOLD(HREF TNEW any)
2213LJFOLDF(fwd_href_tnew)
2214{
2215  if (lj_opt_fwd_href_nokey(J))
2216    return lj_ir_kkptr(J, niltvg(J2G(J)));
2217  return NEXTFOLD;
2218}
2219
2220LJFOLD(HREF TDUP KPRI)
2221LJFOLD(HREF TDUP KGC)
2222LJFOLD(HREF TDUP KNUM)
2223LJFOLDF(fwd_href_tdup)
2224{
2225  TValue keyv;
2226  cTValue *val;
2227  lj_ir_kvalue(J->L, &keyv, fright);
2228  val = lj_tab_get(J->L, ir_ktab(IR(fleft->op1)), &keyv);
2229  /* Check for either nil or the nil value marker in the template table. */
2230  if ((tvisnil(val) || tvistab(val)) && lj_opt_fwd_href_nokey(J))
2231    return lj_ir_kkptr(J, niltvg(J2G(J)));
2232  return NEXTFOLD;
2233}
2234
2235/* We can safely FOLD/CSE array/hash refs and field loads, since there
2236** are no corresponding stores. But we need to check for any NEWREF with
2237** an aliased table, as it may invalidate all of the pointers and fields.
2238** Only HREF needs the NEWREF check -- AREF and HREFK already depend on
2239** FLOADs. And NEWREF itself is treated like a store (see below).
2240** LREF is constant (per trace) since coroutine switches are not inlined.
2241*/
2242LJFOLD(FLOAD TNEW IRFL_TAB_ASIZE)
2243LJFOLDF(fload_tab_tnew_asize)
2244{
2245  if (LJ_LIKELY(J->flags & JIT_F_OPT_FOLD) && lj_opt_fwd_tptr(J, fins->op1))
2246    return INTFOLD(fleft->op1);
2247  return NEXTFOLD;
2248}
2249
2250LJFOLD(FLOAD TNEW IRFL_TAB_HMASK)
2251LJFOLDF(fload_tab_tnew_hmask)
2252{
2253  if (LJ_LIKELY(J->flags & JIT_F_OPT_FOLD) && lj_opt_fwd_tptr(J, fins->op1))
2254    return INTFOLD((1 << fleft->op2)-1);
2255  return NEXTFOLD;
2256}
2257
2258LJFOLD(FLOAD TDUP IRFL_TAB_ASIZE)
2259LJFOLDF(fload_tab_tdup_asize)
2260{
2261  if (LJ_LIKELY(J->flags & JIT_F_OPT_FOLD) && lj_opt_fwd_tptr(J, fins->op1))
2262    return INTFOLD((int32_t)ir_ktab(IR(fleft->op1))->asize);
2263  return NEXTFOLD;
2264}
2265
2266LJFOLD(FLOAD TDUP IRFL_TAB_HMASK)
2267LJFOLDF(fload_tab_tdup_hmask)
2268{
2269  if (LJ_LIKELY(J->flags & JIT_F_OPT_FOLD) && lj_opt_fwd_tptr(J, fins->op1))
2270    return INTFOLD((int32_t)ir_ktab(IR(fleft->op1))->hmask);
2271  return NEXTFOLD;
2272}
2273
2274LJFOLD(HREF any any)
2275LJFOLD(FLOAD any IRFL_TAB_ARRAY)
2276LJFOLD(FLOAD any IRFL_TAB_NODE)
2277LJFOLD(FLOAD any IRFL_TAB_ASIZE)
2278LJFOLD(FLOAD any IRFL_TAB_HMASK)
2279LJFOLDF(fload_tab_ah)
2280{
2281  TRef tr = lj_opt_cse(J);
2282  return lj_opt_fwd_tptr(J, tref_ref(tr)) ? tr : EMITFOLD;
2283}
2284
2285/* Strings are immutable, so we can safely FOLD/CSE the related FLOAD. */
2286LJFOLD(FLOAD KGC IRFL_STR_LEN)
2287LJFOLDF(fload_str_len_kgc)
2288{
2289  if (LJ_LIKELY(J->flags & JIT_F_OPT_FOLD))
2290    return INTFOLD((int32_t)ir_kstr(fleft)->len);
2291  return NEXTFOLD;
2292}
2293
2294LJFOLD(FLOAD SNEW IRFL_STR_LEN)
2295LJFOLDF(fload_str_len_snew)
2296{
2297  if (LJ_LIKELY(J->flags & JIT_F_OPT_FOLD)) {
2298    PHIBARRIER(fleft);
2299    return fleft->op2;
2300  }
2301  return NEXTFOLD;
2302}
2303
2304LJFOLD(FLOAD TOSTR IRFL_STR_LEN)
2305LJFOLDF(fload_str_len_tostr)
2306{
2307  if (LJ_LIKELY(J->flags & JIT_F_OPT_FOLD) && fleft->op2 == IRTOSTR_CHAR)
2308    return INTFOLD(1);
2309  return NEXTFOLD;
2310}
2311
2312LJFOLD(FLOAD any IRFL_SBUF_W)
2313LJFOLD(FLOAD any IRFL_SBUF_E)
2314LJFOLD(FLOAD any IRFL_SBUF_B)
2315LJFOLD(FLOAD any IRFL_SBUF_L)
2316LJFOLD(FLOAD any IRFL_SBUF_REF)
2317LJFOLD(FLOAD any IRFL_SBUF_R)
2318LJFOLDF(fload_sbuf)
2319{
2320  TRef tr = lj_opt_fwd_fload(J);
2321  return lj_opt_fwd_sbuf(J, tref_ref(tr)) ? tr : EMITFOLD;
2322}
2323
2324/* The fast function ID of function objects is immutable. */
2325LJFOLD(FLOAD KGC IRFL_FUNC_FFID)
2326LJFOLDF(fload_func_ffid_kgc)
2327{
2328  if (LJ_LIKELY(J->flags & JIT_F_OPT_FOLD))
2329    return INTFOLD((int32_t)ir_kfunc(fleft)->c.ffid);
2330  return NEXTFOLD;
2331}
2332
2333/* The C type ID of cdata objects is immutable. */
2334LJFOLD(FLOAD KGC IRFL_CDATA_CTYPEID)
2335LJFOLDF(fload_cdata_typeid_kgc)
2336{
2337  if (LJ_LIKELY(J->flags & JIT_F_OPT_FOLD))
2338    return INTFOLD((int32_t)ir_kcdata(fleft)->ctypeid);
2339  return NEXTFOLD;
2340}
2341
2342/* Get the contents of immutable cdata objects. */
2343LJFOLD(FLOAD KGC IRFL_CDATA_PTR)
2344LJFOLD(FLOAD KGC IRFL_CDATA_INT)
2345LJFOLD(FLOAD KGC IRFL_CDATA_INT64)
2346LJFOLDF(fload_cdata_int64_kgc)
2347{
2348  if (LJ_LIKELY(J->flags & JIT_F_OPT_FOLD)) {
2349    void *p = cdataptr(ir_kcdata(fleft));
2350    if (irt_is64(fins->t))
2351      return INT64FOLD(*(uint64_t *)p);
2352    else
2353      return INTFOLD(*(int32_t *)p);
2354  }
2355  return NEXTFOLD;
2356}
2357
2358LJFOLD(FLOAD CNEW IRFL_CDATA_CTYPEID)
2359LJFOLD(FLOAD CNEWI IRFL_CDATA_CTYPEID)
2360LJFOLDF(fload_cdata_typeid_cnew)
2361{
2362  if (LJ_LIKELY(J->flags & JIT_F_OPT_FOLD))
2363    return fleft->op1;  /* No PHI barrier needed. CNEW/CNEWI op1 is const. */
2364  return NEXTFOLD;
2365}
2366
2367/* Pointer, int and int64 cdata objects are immutable. */
2368LJFOLD(FLOAD CNEWI IRFL_CDATA_PTR)
2369LJFOLD(FLOAD CNEWI IRFL_CDATA_INT)
2370LJFOLD(FLOAD CNEWI IRFL_CDATA_INT64)
2371LJFOLDF(fload_cdata_ptr_int64_cnew)
2372{
2373  if (LJ_LIKELY(J->flags & JIT_F_OPT_FOLD))
2374    return fleft->op2;  /* Fold even across PHI to avoid allocations. */
2375  return NEXTFOLD;
2376}
2377
2378LJFOLD(FLOAD any IRFL_STR_LEN)
2379LJFOLD(FLOAD any IRFL_FUNC_ENV)
2380LJFOLD(FLOAD any IRFL_THREAD_ENV)
2381LJFOLD(FLOAD any IRFL_CDATA_CTYPEID)
2382LJFOLD(FLOAD any IRFL_CDATA_PTR)
2383LJFOLD(FLOAD any IRFL_CDATA_INT)
2384LJFOLD(FLOAD any IRFL_CDATA_INT64)
2385LJFOLD(VLOAD any any)  /* Vararg loads have no corresponding stores. */
2386LJFOLDX(lj_opt_cse)
2387
2388/* All other field loads need alias analysis. */
2389LJFOLD(FLOAD any any)
2390LJFOLDX(lj_opt_fwd_fload)
2391
2392/* This is for LOOP only. Recording handles SLOADs internally. */
2393LJFOLD(SLOAD any any)
2394LJFOLDF(fwd_sload)
2395{
2396  if ((fins->op2 & IRSLOAD_FRAME)) {
2397    TRef tr = lj_opt_cse(J);
2398    return tref_ref(tr) < J->chain[IR_RETF] ? EMITFOLD : tr;
2399  } else {
2400    lj_assertJ(J->slot[fins->op1] != 0, "uninitialized slot accessed");
2401    return J->slot[fins->op1];
2402  }
2403}
2404
2405/* Only fold for KKPTR. The pointer _and_ the contents must be const. */
2406LJFOLD(XLOAD KKPTR any)
2407LJFOLDF(xload_kptr)
2408{
2409  TRef tr = kfold_xload(J, fins, ir_kptr(fleft));
2410  return tr ? tr : NEXTFOLD;
2411}
2412
2413LJFOLD(XLOAD any any)
2414LJFOLDX(lj_opt_fwd_xload)
2415
2416/* -- Frame handling ------------------------------------------------------ */
2417
2418/* Prevent CSE of a REF_BASE operand across IR_RETF. */
2419LJFOLD(SUB any BASE)
2420LJFOLD(SUB BASE any)
2421LJFOLD(EQ any BASE)
2422LJFOLDF(fold_base)
2423{
2424  return lj_opt_cselim(J, J->chain[IR_RETF]);
2425}
2426
2427/* -- Write barriers ------------------------------------------------------ */
2428
2429/* Write barriers are amenable to CSE, but not across any incremental
2430** GC steps.
2431*/
2432LJFOLD(TBAR any)
2433LJFOLD(OBAR any any)
2434LJFOLDF(barrier_tab)
2435{
2436  TRef tr = lj_opt_cse(J);
2437  if (gcstep_barrier(J, tref_ref(tr)))  /* CSE across GC step? */
2438    return EMITFOLD;  /* Raw emit. Assumes fins is left intact by CSE. */
2439  return tr;
2440}
2441
2442LJFOLD(TBAR TNEW)
2443LJFOLD(TBAR TDUP)
2444LJFOLDF(barrier_tnew_tdup)
2445{
2446  /* New tables are always white and never need a barrier. */
2447  if (fins->op1 < J->chain[IR_LOOP])  /* Except across a GC step. */
2448    return NEXTFOLD;
2449  return DROPFOLD;
2450}
2451
2452/* -- Profiling ----------------------------------------------------------- */
2453
2454LJFOLD(PROF any any)
2455LJFOLDF(prof)
2456{
2457  IRRef ref = J->chain[IR_PROF];
2458  if (ref+1 == J->cur.nins)  /* Drop neighbouring IR_PROF. */
2459    return ref;
2460  return EMITFOLD;
2461}
2462
2463/* -- Stores and allocations ---------------------------------------------- */
2464
2465/* Stores and allocations cannot be folded or passed on to CSE in general.
2466** But some stores can be eliminated with dead-store elimination (DSE).
2467**
2468** Caveat: *all* stores and allocs must be listed here or they end up at CSE!
2469*/
2470
2471LJFOLD(ASTORE any any)
2472LJFOLD(HSTORE any any)
2473LJFOLDX(lj_opt_dse_ahstore)
2474
2475LJFOLD(USTORE any any)
2476LJFOLDX(lj_opt_dse_ustore)
2477
2478LJFOLD(FSTORE any any)
2479LJFOLDX(lj_opt_dse_fstore)
2480
2481LJFOLD(XSTORE any any)
2482LJFOLDX(lj_opt_dse_xstore)
2483
2484LJFOLD(NEWREF any any)  /* Treated like a store. */
2485LJFOLD(TMPREF any any)
2486LJFOLD(CALLA any any)
2487LJFOLD(CALLL any any)  /* Safeguard fallback. */
2488LJFOLD(CALLS any any)
2489LJFOLD(CALLXS any any)
2490LJFOLD(XBAR)
2491LJFOLD(RETF any any)  /* Modifies BASE. */
2492LJFOLD(TNEW any any)
2493LJFOLD(TDUP any)
2494LJFOLD(CNEW any any)
2495LJFOLD(XSNEW any any)
2496LJFOLDX(lj_ir_emit)
2497
2498/* -- Miscellaneous ------------------------------------------------------- */
2499
2500LJFOLD(CARG any any)
2501LJFOLDF(cse_carg)
2502{
2503  TRef tr = lj_opt_cse(J);
2504  if (tref_ref(tr) < J->chain[IR_LOOP])  /* CSE across loop? */
2505    return EMITFOLD;  /* Raw emit. Assumes fins is left intact by CSE. */
2506  return tr;
2507}
2508
2509/* ------------------------------------------------------------------------ */
2510
2511/* Every entry in the generated hash table is a 32 bit pattern:
2512**
2513** xxxxxxxx iiiiiii lllllll rrrrrrrrrr
2514**
2515**   xxxxxxxx = 8 bit index into fold function table
2516**    iiiiiii = 7 bit folded instruction opcode
2517**    lllllll = 7 bit left instruction opcode
2518** rrrrrrrrrr = 8 bit right instruction opcode or 10 bits from literal field
2519*/
2520
2521#include "lj_folddef.h"
2522
2523/* ------------------------------------------------------------------------ */
2524
2525/* Fold IR instruction. */
2526TRef LJ_FASTCALL lj_opt_fold(jit_State *J)
2527{
2528  uint32_t key, any;
2529  IRRef ref;
2530
2531  if (LJ_UNLIKELY((J->flags & JIT_F_OPT_MASK) != JIT_F_OPT_DEFAULT)) {
2532    lj_assertJ(((JIT_F_OPT_FOLD|JIT_F_OPT_FWD|JIT_F_OPT_CSE|JIT_F_OPT_DSE) |
2533		JIT_F_OPT_DEFAULT) == JIT_F_OPT_DEFAULT,
2534	       "bad JIT_F_OPT_DEFAULT");
2535    /* Folding disabled? Chain to CSE, but not for loads/stores/allocs. */
2536    if (!(J->flags & JIT_F_OPT_FOLD) && irm_kind(lj_ir_mode[fins->o]) == IRM_N)
2537      return lj_opt_cse(J);
2538
2539    /* No FOLD, forwarding or CSE? Emit raw IR for loads, except for SLOAD. */
2540    if ((J->flags & (JIT_F_OPT_FOLD|JIT_F_OPT_FWD|JIT_F_OPT_CSE)) !=
2541		    (JIT_F_OPT_FOLD|JIT_F_OPT_FWD|JIT_F_OPT_CSE) &&
2542	irm_kind(lj_ir_mode[fins->o]) == IRM_L && fins->o != IR_SLOAD)
2543      return lj_ir_emit(J);
2544
2545    /* No FOLD or DSE? Emit raw IR for stores. */
2546    if ((J->flags & (JIT_F_OPT_FOLD|JIT_F_OPT_DSE)) !=
2547		    (JIT_F_OPT_FOLD|JIT_F_OPT_DSE) &&
2548	irm_kind(lj_ir_mode[fins->o]) == IRM_S)
2549      return lj_ir_emit(J);
2550  }
2551
2552  /* Fold engine start/retry point. */
2553retry:
2554  /* Construct key from opcode and operand opcodes (unless literal/none). */
2555  key = ((uint32_t)fins->o << 17);
2556  if (fins->op1 >= J->cur.nk) {
2557    key += (uint32_t)IR(fins->op1)->o << 10;
2558    *fleft = *IR(fins->op1);
2559    if (fins->op1 < REF_TRUE)
2560      fleft[1] = IR(fins->op1)[1];
2561  }
2562  if (fins->op2 >= J->cur.nk) {
2563    key += (uint32_t)IR(fins->op2)->o;
2564    *fright = *IR(fins->op2);
2565    if (fins->op2 < REF_TRUE)
2566      fright[1] = IR(fins->op2)[1];
2567  } else {
2568    key += (fins->op2 & 0x3ffu);  /* Literal mask. Must include IRCONV_*MASK. */
2569  }
2570
2571  /* Check for a match in order from most specific to least specific. */
2572  any = 0;
2573  for (;;) {
2574    uint32_t k = key | (any & 0x1ffff);
2575    uint32_t h = fold_hashkey(k);
2576    uint32_t fh = fold_hash[h];  /* Lookup key in semi-perfect hash table. */
2577    if ((fh & 0xffffff) == k || (fh = fold_hash[h+1], (fh & 0xffffff) == k)) {
2578      ref = (IRRef)tref_ref(fold_func[fh >> 24](J));
2579      if (ref != NEXTFOLD)
2580	break;
2581    }
2582    if (any == 0xfffff)  /* Exhausted folding. Pass on to CSE. */
2583      return lj_opt_cse(J);
2584    any = (any | (any >> 10)) ^ 0xffc00;
2585  }
2586
2587  /* Return value processing, ordered by frequency. */
2588  if (LJ_LIKELY(ref >= MAX_FOLD))
2589    return TREF(ref, irt_t(IR(ref)->t));
2590  if (ref == RETRYFOLD)
2591    goto retry;
2592  if (ref == KINTFOLD)
2593    return lj_ir_kint(J, fins->i);
2594  if (ref == FAILFOLD)
2595    lj_trace_err(J, LJ_TRERR_GFAIL);
2596  lj_assertJ(ref == DROPFOLD, "bad fold result");
2597  return REF_DROP;
2598}
2599
2600/* -- Common-Subexpression Elimination ------------------------------------ */
2601
2602/* CSE an IR instruction. This is very fast due to the skip-list chains. */
2603TRef LJ_FASTCALL lj_opt_cse(jit_State *J)
2604{
2605  /* Avoid narrow to wide store-to-load forwarding stall */
2606  IRRef2 op12 = (IRRef2)fins->op1 + ((IRRef2)fins->op2 << 16);
2607  IROp op = fins->o;
2608  if (LJ_LIKELY(J->flags & JIT_F_OPT_CSE)) {
2609    /* Limited search for same operands in per-opcode chain. */
2610    IRRef ref = J->chain[op];
2611    IRRef lim = fins->op1;
2612    if (fins->op2 > lim) lim = fins->op2;  /* Relies on lit < REF_BIAS. */
2613    while (ref > lim) {
2614      if (IR(ref)->op12 == op12)
2615	return TREF(ref, irt_t(IR(ref)->t));  /* Common subexpression found. */
2616      ref = IR(ref)->prev;
2617    }
2618  }
2619  /* Otherwise emit IR (inlined for speed). */
2620  {
2621    IRRef ref = lj_ir_nextins(J);
2622    IRIns *ir = IR(ref);
2623    ir->prev = J->chain[op];
2624    ir->op12 = op12;
2625    J->chain[op] = (IRRef1)ref;
2626    ir->o = fins->o;
2627    J->guardemit.irt |= fins->t.irt;
2628    return TREF(ref, irt_t((ir->t = fins->t)));
2629  }
2630}
2631
2632/* CSE with explicit search limit. */
2633TRef LJ_FASTCALL lj_opt_cselim(jit_State *J, IRRef lim)
2634{
2635  IRRef ref = J->chain[fins->o];
2636  IRRef2 op12 = (IRRef2)fins->op1 + ((IRRef2)fins->op2 << 16);
2637  while (ref > lim) {
2638    if (IR(ref)->op12 == op12)
2639      return ref;
2640    ref = IR(ref)->prev;
2641  }
2642  return lj_ir_emit(J);
2643}
2644
2645/* ------------------------------------------------------------------------ */
2646
2647#undef IR
2648#undef fins
2649#undef fleft
2650#undef fright
2651#undef knumleft
2652#undef knumright
2653#undef emitir
2654
2655#endif