1 /*
2 ** LOOP: Loop Optimizations.
3 ** Copyright (C) 2005-2021 Mike Pall. See Copyright Notice in luajit.h
4 */
5 
6 #define lj_opt_loop_c
7 #define LUA_CORE
8 
9 #include "lj_obj.h"
10 
11 #if LJ_HASJIT
12 
13 #include "lj_err.h"
14 #include "lj_buf.h"
15 #include "lj_ir.h"
16 #include "lj_jit.h"
17 #include "lj_iropt.h"
18 #include "lj_trace.h"
19 #include "lj_snap.h"
20 #include "lj_vm.h"
21 
22 /* Loop optimization:
23 **
24 ** Traditional Loop-Invariant Code Motion (LICM) splits the instructions
25 ** of a loop into invariant and variant instructions. The invariant
26 ** instructions are hoisted out of the loop and only the variant
27 ** instructions remain inside the loop body.
28 **
29 ** Unfortunately LICM is mostly useless for compiling dynamic languages.
30 ** The IR has many guards and most of the subsequent instructions are
31 ** control-dependent on them. The first non-hoistable guard would
32 ** effectively prevent hoisting of all subsequent instructions.
33 **
34 ** That's why we use a special form of unrolling using copy-substitution,
35 ** combined with redundancy elimination:
36 **
37 ** The recorded instruction stream is re-emitted to the compiler pipeline
38 ** with substituted operands. The substitution table is filled with the
39 ** refs returned by re-emitting each instruction. This can be done
40 ** on-the-fly, because the IR is in strict SSA form, where every ref is
41 ** defined before its use.
42 **
43 ** This aproach generates two code sections, separated by the LOOP
44 ** instruction:
45 **
46 ** 1. The recorded instructions form a kind of pre-roll for the loop. It
47 ** contains a mix of invariant and variant instructions and performs
48 ** exactly one loop iteration (but not necessarily the 1st iteration).
49 **
50 ** 2. The loop body contains only the variant instructions and performs
51 ** all remaining loop iterations.
52 **
53 ** On first sight that looks like a waste of space, because the variant
54 ** instructions are present twice. But the key insight is that the
55 ** pre-roll honors the control-dependencies for *both* the pre-roll itself
56 ** *and* the loop body!
57 **
58 ** It also means one doesn't have to explicitly model control-dependencies
59 ** (which, BTW, wouldn't help LICM much). And it's much easier to
60 ** integrate sparse snapshotting with this approach.
61 **
62 ** One of the nicest aspects of this approach is that all of the
63 ** optimizations of the compiler pipeline (FOLD, CSE, FWD, etc.) can be
64 ** reused with only minor restrictions (e.g. one should not fold
65 ** instructions across loop-carried dependencies).
66 **
67 ** But in general all optimizations can be applied which only need to look
68 ** backwards into the generated instruction stream. At any point in time
69 ** during the copy-substitution process this contains both a static loop
70 ** iteration (the pre-roll) and a dynamic one (from the to-be-copied
71 ** instruction up to the end of the partial loop body).
72 **
73 ** Since control-dependencies are implicitly kept, CSE also applies to all
74 ** kinds of guards. The major advantage is that all invariant guards can
75 ** be hoisted, too.
76 **
77 ** Load/store forwarding works across loop iterations, too. This is
78 ** important if loop-carried dependencies are kept in upvalues or tables.
79 ** E.g. 'self.idx = self.idx + 1' deep down in some OO-style method may
80 ** become a forwarded loop-recurrence after inlining.
81 **
82 ** Since the IR is in SSA form, loop-carried dependencies have to be
83 ** modeled with PHI instructions. The potential candidates for PHIs are
84 ** collected on-the-fly during copy-substitution. After eliminating the
85 ** redundant ones, PHI instructions are emitted *below* the loop body.
86 **
87 ** Note that this departure from traditional SSA form doesn't change the
88 ** semantics of the PHI instructions themselves. But it greatly simplifies
89 ** on-the-fly generation of the IR and the machine code.
90 */
91 
92 /* Some local macros to save typing. Undef'd at the end. */
93 #define IR(ref)		(&J->cur.ir[(ref)])
94 
95 /* Pass IR on to next optimization in chain (FOLD). */
96 #define emitir(ot, a, b)	(lj_ir_set(J, (ot), (a), (b)), lj_opt_fold(J))
97 
98 /* Emit raw IR without passing through optimizations. */
99 #define emitir_raw(ot, a, b)	(lj_ir_set(J, (ot), (a), (b)), lj_ir_emit(J))
100 
101 /* -- PHI elimination ----------------------------------------------------- */
102 
103 /* Emit or eliminate collected PHIs. */
loop_emit_phi(jit_State * J,IRRef1 * subst,IRRef1 * phi,IRRef nphi,SnapNo onsnap)104 static void loop_emit_phi(jit_State *J, IRRef1 *subst, IRRef1 *phi, IRRef nphi,
105 			  SnapNo onsnap)
106 {
107   int passx = 0;
108   IRRef i, j, nslots;
109   IRRef invar = J->chain[IR_LOOP];
110   /* Pass #1: mark redundant and potentially redundant PHIs. */
111   for (i = 0, j = 0; i < nphi; i++) {
112     IRRef lref = phi[i];
113     IRRef rref = subst[lref];
114     if (lref == rref || rref == REF_DROP) {  /* Invariants are redundant. */
115       irt_clearphi(IR(lref)->t);
116     } else {
117       phi[j++] = (IRRef1)lref;
118       if (!(IR(rref)->op1 == lref || IR(rref)->op2 == lref)) {
119 	/* Quick check for simple recurrences failed, need pass2. */
120 	irt_setmark(IR(lref)->t);
121 	passx = 1;
122       }
123     }
124   }
125   nphi = j;
126   /* Pass #2: traverse variant part and clear marks of non-redundant PHIs. */
127   if (passx) {
128     SnapNo s;
129     for (i = J->cur.nins-1; i > invar; i--) {
130       IRIns *ir = IR(i);
131       if (!irref_isk(ir->op2)) irt_clearmark(IR(ir->op2)->t);
132       if (!irref_isk(ir->op1)) {
133 	irt_clearmark(IR(ir->op1)->t);
134 	if (ir->op1 < invar &&
135 	    ir->o >= IR_CALLN && ir->o <= IR_CARG) {  /* ORDER IR */
136 	  ir = IR(ir->op1);
137 	  while (ir->o == IR_CARG) {
138 	    if (!irref_isk(ir->op2)) irt_clearmark(IR(ir->op2)->t);
139 	    if (irref_isk(ir->op1)) break;
140 	    ir = IR(ir->op1);
141 	    irt_clearmark(ir->t);
142 	  }
143 	}
144       }
145     }
146     for (s = J->cur.nsnap-1; s >= onsnap; s--) {
147       SnapShot *snap = &J->cur.snap[s];
148       SnapEntry *map = &J->cur.snapmap[snap->mapofs];
149       MSize n, nent = snap->nent;
150       for (n = 0; n < nent; n++) {
151 	IRRef ref = snap_ref(map[n]);
152 	if (!irref_isk(ref)) irt_clearmark(IR(ref)->t);
153       }
154     }
155   }
156   /* Pass #3: add PHIs for variant slots without a corresponding SLOAD. */
157   nslots = J->baseslot+J->maxslot;
158   for (i = 1; i < nslots; i++) {
159     IRRef ref = tref_ref(J->slot[i]);
160     while (!irref_isk(ref) && ref != subst[ref]) {
161       IRIns *ir = IR(ref);
162       irt_clearmark(ir->t);  /* Unmark potential uses, too. */
163       if (irt_isphi(ir->t) || irt_ispri(ir->t))
164 	break;
165       irt_setphi(ir->t);
166       if (nphi >= LJ_MAX_PHI)
167 	lj_trace_err(J, LJ_TRERR_PHIOV);
168       phi[nphi++] = (IRRef1)ref;
169       ref = subst[ref];
170       if (ref > invar)
171 	break;
172     }
173   }
174   /* Pass #4: propagate non-redundant PHIs. */
175   while (passx) {
176     passx = 0;
177     for (i = 0; i < nphi; i++) {
178       IRRef lref = phi[i];
179       IRIns *ir = IR(lref);
180       if (!irt_ismarked(ir->t)) {  /* Propagate only from unmarked PHIs. */
181 	IRIns *irr = IR(subst[lref]);
182 	if (irt_ismarked(irr->t)) {  /* Right ref points to other PHI? */
183 	  irt_clearmark(irr->t);  /* Mark that PHI as non-redundant. */
184 	  passx = 1;  /* Retry. */
185 	}
186       }
187     }
188   }
189   /* Pass #5: emit PHI instructions or eliminate PHIs. */
190   for (i = 0; i < nphi; i++) {
191     IRRef lref = phi[i];
192     IRIns *ir = IR(lref);
193     if (!irt_ismarked(ir->t)) {  /* Emit PHI if not marked. */
194       IRRef rref = subst[lref];
195       if (rref > invar)
196 	irt_setphi(IR(rref)->t);
197       emitir_raw(IRT(IR_PHI, irt_type(ir->t)), lref, rref);
198     } else {  /* Otherwise eliminate PHI. */
199       irt_clearmark(ir->t);
200       irt_clearphi(ir->t);
201     }
202   }
203 }
204 
205 /* -- Loop unrolling using copy-substitution ------------------------------ */
206 
207 /* Copy-substitute snapshot. */
loop_subst_snap(jit_State * J,SnapShot * osnap,SnapEntry * loopmap,IRRef1 * subst)208 static void loop_subst_snap(jit_State *J, SnapShot *osnap,
209 			    SnapEntry *loopmap, IRRef1 *subst)
210 {
211   SnapEntry *nmap, *omap = &J->cur.snapmap[osnap->mapofs];
212   SnapEntry *nextmap = &J->cur.snapmap[snap_nextofs(&J->cur, osnap)];
213   MSize nmapofs;
214   MSize on, ln, nn, onent = osnap->nent;
215   BCReg nslots = osnap->nslots;
216   SnapShot *snap = &J->cur.snap[J->cur.nsnap];
217   if (irt_isguard(J->guardemit)) {  /* Guard inbetween? */
218     nmapofs = J->cur.nsnapmap;
219     J->cur.nsnap++;  /* Add new snapshot. */
220   } else {  /* Otherwise overwrite previous snapshot. */
221     snap--;
222     nmapofs = snap->mapofs;
223   }
224   J->guardemit.irt = 0;
225   /* Setup new snapshot. */
226   snap->mapofs = (uint32_t)nmapofs;
227   snap->ref = (IRRef1)J->cur.nins;
228   snap->nslots = nslots;
229   snap->topslot = osnap->topslot;
230   snap->count = 0;
231   nmap = &J->cur.snapmap[nmapofs];
232   /* Substitute snapshot slots. */
233   on = ln = nn = 0;
234   while (on < onent) {
235     SnapEntry osn = omap[on], lsn = loopmap[ln];
236     if (snap_slot(lsn) < snap_slot(osn)) {  /* Copy slot from loop map. */
237       nmap[nn++] = lsn;
238       ln++;
239     } else {  /* Copy substituted slot from snapshot map. */
240       if (snap_slot(lsn) == snap_slot(osn)) ln++;  /* Shadowed loop slot. */
241       if (!irref_isk(snap_ref(osn)))
242 	osn = snap_setref(osn, subst[snap_ref(osn)]);
243       nmap[nn++] = osn;
244       on++;
245     }
246   }
247   while (snap_slot(loopmap[ln]) < nslots)  /* Copy remaining loop slots. */
248     nmap[nn++] = loopmap[ln++];
249   snap->nent = (uint8_t)nn;
250   omap += onent;
251   nmap += nn;
252   while (omap < nextmap)  /* Copy PC + frame links. */
253     *nmap++ = *omap++;
254   J->cur.nsnapmap = (uint32_t)(nmap - J->cur.snapmap);
255 }
256 
257 typedef struct LoopState {
258   jit_State *J;
259   IRRef1 *subst;
260   MSize sizesubst;
261 } LoopState;
262 
263 /* Unroll loop. */
loop_unroll(LoopState * lps)264 static void loop_unroll(LoopState *lps)
265 {
266   jit_State *J = lps->J;
267   IRRef1 phi[LJ_MAX_PHI];
268   uint32_t nphi = 0;
269   IRRef1 *subst;
270   SnapNo onsnap;
271   SnapShot *osnap, *loopsnap;
272   SnapEntry *loopmap, *psentinel;
273   IRRef ins, invar;
274 
275   /* Allocate substitution table.
276   ** Only non-constant refs in [REF_BIAS,invar) are valid indexes.
277   */
278   invar = J->cur.nins;
279   lps->sizesubst = invar - REF_BIAS;
280   lps->subst = lj_mem_newvec(J->L, lps->sizesubst, IRRef1);
281   subst = lps->subst - REF_BIAS;
282   subst[REF_BASE] = REF_BASE;
283 
284   /* LOOP separates the pre-roll from the loop body. */
285   emitir_raw(IRTG(IR_LOOP, IRT_NIL), 0, 0);
286 
287   /* Grow snapshot buffer and map for copy-substituted snapshots.
288   ** Need up to twice the number of snapshots minus #0 and loop snapshot.
289   ** Need up to twice the number of entries plus fallback substitutions
290   ** from the loop snapshot entries for each new snapshot.
291   ** Caveat: both calls may reallocate J->cur.snap and J->cur.snapmap!
292   */
293   onsnap = J->cur.nsnap;
294   lj_snap_grow_buf(J, 2*onsnap-2);
295   lj_snap_grow_map(J, J->cur.nsnapmap*2+(onsnap-2)*J->cur.snap[onsnap-1].nent);
296 
297   /* The loop snapshot is used for fallback substitutions. */
298   loopsnap = &J->cur.snap[onsnap-1];
299   loopmap = &J->cur.snapmap[loopsnap->mapofs];
300   /* The PC of snapshot #0 and the loop snapshot must match. */
301   psentinel = &loopmap[loopsnap->nent];
302   lj_assertJ(*psentinel == J->cur.snapmap[J->cur.snap[0].nent],
303 	     "mismatched PC for loop snapshot");
304   *psentinel = SNAP(255, 0, 0);  /* Replace PC with temporary sentinel. */
305 
306   /* Start substitution with snapshot #1 (#0 is empty for root traces). */
307   osnap = &J->cur.snap[1];
308 
309   /* Copy and substitute all recorded instructions and snapshots. */
310   for (ins = REF_FIRST; ins < invar; ins++) {
311     IRIns *ir;
312     IRRef op1, op2;
313 
314     if (ins >= osnap->ref)  /* Instruction belongs to next snapshot? */
315       loop_subst_snap(J, osnap++, loopmap, subst);  /* Copy-substitute it. */
316 
317     /* Substitute instruction operands. */
318     ir = IR(ins);
319     op1 = ir->op1;
320     if (!irref_isk(op1)) op1 = subst[op1];
321     op2 = ir->op2;
322     if (!irref_isk(op2)) op2 = subst[op2];
323     if (irm_kind(lj_ir_mode[ir->o]) == IRM_N &&
324 	op1 == ir->op1 && op2 == ir->op2) {  /* Regular invariant ins? */
325       subst[ins] = (IRRef1)ins;  /* Shortcut. */
326     } else {
327       /* Re-emit substituted instruction to the FOLD/CSE/etc. pipeline. */
328       IRType1 t = ir->t;  /* Get this first, since emitir may invalidate ir. */
329       IRRef ref = tref_ref(emitir(ir->ot & ~IRT_ISPHI, op1, op2));
330       subst[ins] = (IRRef1)ref;
331       if (ref != ins) {
332 	IRIns *irr = IR(ref);
333 	if (ref < invar) {  /* Loop-carried dependency? */
334 	  /* Potential PHI? */
335 	  if (!irref_isk(ref) && !irt_isphi(irr->t) && !irt_ispri(irr->t)) {
336 	    irt_setphi(irr->t);
337 	    if (nphi >= LJ_MAX_PHI)
338 	      lj_trace_err(J, LJ_TRERR_PHIOV);
339 	    phi[nphi++] = (IRRef1)ref;
340 	  }
341 	  /* Check all loop-carried dependencies for type instability. */
342 	  if (!irt_sametype(t, irr->t)) {
343 	    if (irt_isinteger(t) && irt_isinteger(irr->t))
344 	      continue;
345 	    else if (irt_isnum(t) && irt_isinteger(irr->t))  /* Fix int->num. */
346 	      ref = tref_ref(emitir(IRTN(IR_CONV), ref, IRCONV_NUM_INT));
347 	    else if (irt_isnum(irr->t) && irt_isinteger(t))  /* Fix num->int. */
348 	      ref = tref_ref(emitir(IRTGI(IR_CONV), ref,
349 				    IRCONV_INT_NUM|IRCONV_CHECK));
350 	    else
351 	      lj_trace_err(J, LJ_TRERR_TYPEINS);
352 	    subst[ins] = (IRRef1)ref;
353 	    irr = IR(ref);
354 	    goto phiconv;
355 	  }
356 	} else if (ref != REF_DROP && ref > invar &&
357 		   ((irr->o == IR_CONV && irr->op1 < invar) ||
358 		    (irr->o == IR_ALEN && irr->op2 < invar &&
359 					  irr->op2 != REF_NIL))) {
360 	  /* May need an extra PHI for a CONV or ALEN hint. */
361 	  ref = irr->o == IR_CONV ? irr->op1 : irr->op2;
362 	  irr = IR(ref);
363 	phiconv:
364 	  if (ref < invar && !irref_isk(ref) && !irt_isphi(irr->t)) {
365 	    irt_setphi(irr->t);
366 	    if (nphi >= LJ_MAX_PHI)
367 	      lj_trace_err(J, LJ_TRERR_PHIOV);
368 	    phi[nphi++] = (IRRef1)ref;
369 	  }
370 	}
371       }
372     }
373   }
374   if (!irt_isguard(J->guardemit))  /* Drop redundant snapshot. */
375     J->cur.nsnapmap = (uint32_t)J->cur.snap[--J->cur.nsnap].mapofs;
376   lj_assertJ(J->cur.nsnapmap <= J->sizesnapmap, "bad snapshot map index");
377   *psentinel = J->cur.snapmap[J->cur.snap[0].nent];  /* Restore PC. */
378 
379   loop_emit_phi(J, subst, phi, nphi, onsnap);
380 }
381 
382 /* Undo any partial changes made by the loop optimization. */
loop_undo(jit_State * J,IRRef ins,SnapNo nsnap,MSize nsnapmap)383 static void loop_undo(jit_State *J, IRRef ins, SnapNo nsnap, MSize nsnapmap)
384 {
385   ptrdiff_t i;
386   SnapShot *snap = &J->cur.snap[nsnap-1];
387   SnapEntry *map = J->cur.snapmap;
388   map[snap->mapofs + snap->nent] = map[J->cur.snap[0].nent];  /* Restore PC. */
389   J->cur.nsnapmap = (uint32_t)nsnapmap;
390   J->cur.nsnap = nsnap;
391   J->guardemit.irt = 0;
392   lj_ir_rollback(J, ins);
393   for (i = 0; i < BPROP_SLOTS; i++) {  /* Remove backprop. cache entries. */
394     BPropEntry *bp = &J->bpropcache[i];
395     if (bp->val >= ins)
396       bp->key = 0;
397   }
398   for (ins--; ins >= REF_FIRST; ins--) {  /* Remove flags. */
399     IRIns *ir = IR(ins);
400     irt_clearphi(ir->t);
401     irt_clearmark(ir->t);
402   }
403 }
404 
405 /* Protected callback for loop optimization. */
cploop_opt(lua_State * L,lua_CFunction dummy,void * ud)406 static TValue *cploop_opt(lua_State *L, lua_CFunction dummy, void *ud)
407 {
408   UNUSED(L); UNUSED(dummy);
409   loop_unroll((LoopState *)ud);
410   return NULL;
411 }
412 
413 /* Loop optimization. */
lj_opt_loop(jit_State * J)414 int lj_opt_loop(jit_State *J)
415 {
416   IRRef nins = J->cur.nins;
417   SnapNo nsnap = J->cur.nsnap;
418   MSize nsnapmap = J->cur.nsnapmap;
419   LoopState lps;
420   int errcode;
421   lps.J = J;
422   lps.subst = NULL;
423   lps.sizesubst = 0;
424   errcode = lj_vm_cpcall(J->L, NULL, &lps, cploop_opt);
425   lj_mem_freevec(J2G(J), lps.subst, lps.sizesubst, IRRef1);
426   if (LJ_UNLIKELY(errcode)) {
427     lua_State *L = J->L;
428     if (errcode == LUA_ERRRUN && tvisnumber(L->top-1)) {  /* Trace error? */
429       int32_t e = numberVint(L->top-1);
430       switch ((TraceError)e) {
431       case LJ_TRERR_TYPEINS:  /* Type instability. */
432       case LJ_TRERR_GFAIL:  /* Guard would always fail. */
433 	/* Unrolling via recording fixes many cases, e.g. a flipped boolean. */
434 	if (--J->instunroll < 0)  /* But do not unroll forever. */
435 	  break;
436 	L->top--;  /* Remove error object. */
437 	loop_undo(J, nins, nsnap, nsnapmap);
438 	return 1;  /* Loop optimization failed, continue recording. */
439       default:
440 	break;
441       }
442     }
443     lj_err_throw(L, errcode);  /* Propagate all other errors. */
444   }
445   return 0;  /* Loop optimization is ok. */
446 }
447 
448 #undef IR
449 #undef emitir
450 #undef emitir_raw
451 
452 #endif
453