aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/libraries/LuaJIT-1.1.7/jit/opt.lua
diff options
context:
space:
mode:
Diffstat (limited to 'libraries/LuaJIT-1.1.7/jit/opt.lua')
-rw-r--r--libraries/LuaJIT-1.1.7/jit/opt.lua508
1 files changed, 0 insertions, 508 deletions
diff --git a/libraries/LuaJIT-1.1.7/jit/opt.lua b/libraries/LuaJIT-1.1.7/jit/opt.lua
deleted file mode 100644
index 5fe0f34..0000000
--- a/libraries/LuaJIT-1.1.7/jit/opt.lua
+++ /dev/null
@@ -1,508 +0,0 @@
1----------------------------------------------------------------------------
2-- LuaJIT optimizer.
3--
4-- Copyright (C) 2005-2011 Mike Pall. All rights reserved.
5-- Released under the MIT/X license. See luajit.h for full copyright notice.
6----------------------------------------------------------------------------
7-- This module contains a simple optimizer that generates some hints for
8-- the compiler backend.
9--
10-- Compare: luajit -j dump -e 'return 1'
11-- with: luajit -O -j dumphints -j dump -e 'return 1'
12--
13-- This module uses a very simplistic (but fast) abstract interpretation
14-- algorithm. It mostly ignores control flow and/or basic block boundaries.
15-- Thus the results of the analysis are really only predictions (e.g. about
16-- monomorphic use of operators). The backend _must_ check all contracts
17-- (e.g. verify the object type) and use a (polymorphic) fallback or
18-- deoptimization in case a contract is broken.
19--
20-- Although simplistic, the generated hints are pretty accurate. Note that
21-- some hints are really definitive and don't need to be checked (like
22-- COMBINE or FOR_STEP_K).
23--
24-- TODO: Try MFP with an extended lattice. But it's unclear whether the
25-- added complexity really pays off with the current backend.
26------------------------------------------------------------------------------
27
28-- Priority for compiler pipeline. Right in the middle before the backend.
29local PRIORITY = 50
30
31-- Default optimizer level, i.e. what you get with -O.
32-- Caveat: this may change in the future when more optimizations are added.
33local OPTLEVEL = 2
34
35-- Heuristic limits for what the compiler should reasonably handle.
36-- Functions outside these limits are unlikely to be run more than once.
37-- Maybe a bit on the generous side. Check ljit.h for backend limits, too.
38-- TODO: make it depend on the bytecode distribution, too.
39local LIMITS = {
40 bytecodes = 4000,
41 stackslots = 150,
42 params = 20,
43 consts = 200,
44 subs = 30,
45}
46
47-- Cache some library functions and objects.
48local jit = require("jit")
49assert(jit.version_num == 10107, "LuaJIT core/library version mismatch")
50local jutil = require("jit.util")
51local type, rawget, next, pcall = type, rawget, next, pcall
52local bytecode, const = jutil.bytecode, jutil.const
53local hints, fhints = jutil.hints, jutil.fhints
54local getmetatable = getmetatable
55
56-- Turn compilation off for the whole module. LuaJIT would do that anyway.
57jit.off(true, true)
58
59-- Default optimizer level after loading. But -O runs setlevel(), too.
60local optlevel = -1
61
62
63-- Use iterative path marking to mark live instructions and branch targets.
64local function marklive(func)
65 local live, work, workn, pc = {}, {}, 0, 1
66 repeat
67 repeat
68 local op, a, b, c, test = bytecode(func, pc)
69 live[pc] = true
70 pc = pc + 1
71 if op == "JMP" then
72 pc = pc + b
73 live[-pc] = true
74 elseif op == "FORLOOP" then
75 local mpc = -pc
76 live[mpc - b] = true
77 live[mpc] = true
78 elseif op == "RETURN" then
79 break
80 elseif test then
81 local fpc = pc + 1
82 -- No need for fallthrough target mark live[-fpc] in our analysis.
83 if not live[fpc] then -- Add fallthrough path to work list.
84 workn = workn + 1
85 work[workn] = fpc
86 end
87 elseif op == "CLOSURE" then
88 pc = pc + jutil.closurenup(func, b) -- Do not mark pseudo-ins live.
89 elseif op == "LOADBOOL" and c ~= 0 then
90 pc = pc + 1
91 live[-pc] = true
92 elseif op == "SETLIST" and c == 0 then
93 pc = pc + 1 -- Do not mark pseudo-ins live.
94 end
95 until live[pc]
96 if workn == 0 then return live end -- Return if work list is empty.
97 pc = work[workn] -- Else fetch next path to mark from work list.
98 workn = workn - 1
99 until false
100end
101
102
103-- Empty objects.
104local function empty() end
105
106-- Dummy function to set call hints. Replaced when jit.opt_inline is loaded.
107local function callhint(st, slot, pc, base, narg, nres)
108 st[pc+hints.TYPE] = slot[base]
109 for i=base,base+nres-1 do slot[i] = nil end
110end
111
112-- Set TYPE hint, but only for numbers, strings or tables.
113local function typehint(st, pc, o)
114 local tp = type(o)
115 if tp == "number" or tp == "string" or tp == "table" then
116 st[pc+hints.TYPE] = o
117 end
118end
119
120-- Set TYPE and TYPEKEY hints for table operations.
121local function tablehint(st, slot, pc, t, kslot)
122 local tp = type(t)
123 if tp == "table" or tp == "userdata" then st[pc+hints.TYPE] = t end
124 if kslot >= 0 then -- Don't need this hint for constants.
125 local key = slot[kslot]
126 local tp = type(key)
127 if tp == "number" or tp == "string" then st[pc+hints.TYPEKEY] = key end
128 end
129end
130
131-- Try to lookup a value. Guess the value or at least the value type.
132local function trylookup(st, t, k)
133 if k == nil then return nil end
134 if type(t) == "table" then
135 local v = rawget(t, k)
136 if v ~= nil then return v end
137 end
138 local mt = getmetatable(t)
139 if type(mt) == "table" then
140 -- One __index level is enough for our purposes.
141 local it = rawget(mt, "__index")
142 if type(it) == "table" then
143 local v = rawget(it, k)
144 if v ~= nil then return v end
145 end
146 end
147 local v = st.tableval[t] -- Resort to a generic guess.
148 if v == nil and type(t) == "table" then v = next(t) end -- Getting desperate.
149 return v
150end
151
152-- Check whether the previous instruction sets a const.
153local function prevconst(st, slot, pc, reg)
154 if st.live[-pc] == nil then -- Current instruction must not be a target.
155 local op, ka, kb = bytecode(st.func, pc-1)
156 if ka == reg and (op == "LOADK" or op == "LOADBOOL" or
157 (op == "LOADNIL" and kb == reg)) then
158 return true, slot[reg]
159 end
160 end
161end
162
163-- Common handler for arithmetic and comparison opcodes.
164local function arithop(st, slot, pc, a, b, c, op)
165 local sb, sc = slot[b], slot[c]
166 if sb == nil then sb = sc elseif sc == nil then sc = sb end
167 local tb, tc = type(sb), type(sc)
168 if tb == tc then
169 if tb == "number" then -- Improve the guess for numbers.
170 if op == "DIV" or sb % 1 ~= 0 or sc % 1 ~= 0 then
171 sb = 0.5 -- Probably a non-integral number.
172 else
173 sb = 1 -- Optimistic guess.
174 end
175 end
176 if sb ~= nil then st[pc+hints.TYPE] = sb end
177 else
178 st[pc+hints.TYPE] = false -- Marker for mixed types.
179 end
180 if op ~= "LT" and op ~= "LE" then
181 slot[a] = sb -- Assume coercion to 1st type if different.
182 end
183end
184
185-- Common handler for TEST and TESTSET.
186local function testop(st, slot, pc, a, b, c)
187 -- Optimize the 'expr and k1 or k2' idiom.
188 local ok, k = prevconst(st, slot, pc, b)
189 if k and a == b then
190 st[pc+hints.COMBINE] = false -- Kill the TEST/TESTSET.
191 if c == 0 then st.live[pc+1] = nil end -- Kill the JMP.
192 end
193 slot[a] = slot[b]
194end
195
196-- Dispatch table for opcode handlers.
197local handler = {
198 MOVE = function(st, slot, pc, a, b, c)
199 slot[a] = slot[b]
200 end,
201
202 LOADK = function(st, slot, pc, a, b, c)
203 slot[a] = const(st.func, b)
204 end,
205
206 LOADBOOL = function(st, slot, pc, a, b, c)
207 slot[a] = (b == 1)
208 end,
209
210 LOADNIL = function(st, slot, pc, a, b, c)
211 for i=a,b do slot[i] = nil end
212 end,
213
214 GETUPVAL = function(st, slot, pc, a, b, c)
215 slot[a] = jutil.upvalue(st.func, b)
216 end,
217
218 GETGLOBAL = function(st, slot, pc, a, b, c)
219 slot[a] = trylookup(st, st.stats.env, const(st.func, b))
220 end,
221
222 GETTABLE = function(st, slot, pc, a, b, c)
223 local t = slot[b]
224 tablehint(st, slot, pc, t, c)
225 slot[a] = trylookup(st, t, slot[c])
226 end,
227
228 SETGLOBAL = empty,
229
230 SETUPVAL = empty, -- TODO: shortcut -- but this is rare?
231
232 SETTABLE = function(st, slot, pc, a, b, c)
233 local t = slot[a]
234 tablehint(st, slot, pc, t, b)
235 if type(t) == "table" or type(t) == "userdata" then -- Must validate setkey.
236 local val = slot[c]
237 if val ~= nil then st.tableval[t] = val end
238 end
239 end,
240
241 NEWTABLE = function(st, slot, pc, a, b, c)
242 slot[a] = {} -- Need unique tables for indexing st.tableval.
243 end,
244
245 SELF = function(st, slot, pc, a, b, c)
246 local t = slot[b]
247 tablehint(st, slot, pc, t, c)
248 slot[a+1] = t
249 slot[a] = trylookup(st, t, slot[c])
250 end,
251
252 ADD = arithop, SUB = arithop, MUL = arithop, DIV = arithop,
253 MOD = arithop, POW = arithop, LT = arithop, LE = arithop,
254
255 UNM = function(st, slot, pc, a, b, c)
256 return arithop(st, slot, pc, a, b, b, "UNM")
257 end,
258
259 NOT = function(st, slot, pc, a, b, c)
260 slot[a] = true
261 end,
262
263 LEN = function(st, slot, pc, a, b, c)
264 typehint(st, pc, slot[b])
265 slot[a] = 1
266 end,
267
268 CONCAT = function(st, slot, pc, a, b, c)
269 local mixed
270 local sb = slot[b]
271 for i=b+1,c do
272 local si = slot[i]
273 if sb == nil then
274 sb = si
275 elseif si ~= nil and type(sb) ~= type(si) then
276 mixed = true
277 break
278 end
279 end
280 if sb == nil then
281 sb = ""
282 else
283 st[pc+hints.TYPE] = not mixed and sb or false
284 if type(sb) == "number" then sb = "" end
285 end
286 slot[a] = sb -- Assume coercion to 1st type (if different) or string.
287 end,
288
289 JMP = function(st, slot, pc, a, b, c)
290 if b >= 0 then -- Kill JMPs across dead code.
291 local tpc = pc + b
292 while not st.live[tpc] do tpc = tpc - 1 end
293 if tpc == pc then st[pc+hints.COMBINE] = false end
294 end
295 end,
296
297 EQ = function(st, slot, pc, a, b, c)
298 if b >= 0 and c >= 0 then typehint(st, pc, slot[b] or slot[c]) end
299 end,
300
301 TEST = function(st, slot, pc, a, b, c)
302 return testop(st, slot, pc, a, a, c)
303 end,
304
305 TESTSET = testop,
306
307 CALL = function(st, slot, pc, a, b, c)
308 callhint(st, slot, pc, a, b-1, c-1)
309 end,
310
311 TAILCALL = function(st, slot, pc, a, b, c)
312 callhint(st, slot, pc, a, b-1, -1)
313 end,
314
315 RETURN = function(st, slot, pc, a, b, c)
316 if b == 2 and prevconst(st, slot, pc, a) then
317 st[pc-1+hints.COMBINE] = true -- Set COMBINE hint for prev. instruction.
318 end
319 end,
320
321 FORLOOP = empty,
322
323 FORPREP = function(st, slot, pc, a, b, c)
324 local ok, step = prevconst(st, slot, pc, a+2)
325 if type(step) == "number" then
326 st[pc+hints.FOR_STEP_K] = step
327 end
328 local nstart, nstep = slot[a], slot[a+2]
329 local tnstart, tnstep = type(nstart), type(nstep)
330 local ntype = ((tnstart == "number" and nstart % 1 ~= 0) or
331 (tnstep == "number" and nstep % 1 ~= 0)) and 0.5 or 1
332 slot[a+3] = ntype
333 if tnstart == "number" and tnstep == "number" and
334 type(slot[a+1]) == "number" then
335 st[pc+hints.TYPE] = ntype
336 end
337 end,
338
339 -- TFORLOOP is at the end of the loop. Setting slots would be pointless.
340 -- Inlining is handled by the corresponding iterator constructor (CALL).
341 TFORLOOP = function(st, slot, pc, a, b, c)
342 st[pc+hints.TYPE] = slot[a]
343 end,
344
345 SETLIST = function(st, slot, pc, a, b, c)
346 -- TODO: if only (numeric) const: shortcut (+ nobarrier).
347 local t = slot[a]
348 -- Very imprecise. But better than nothing.
349 if type(t) == "table" then st.tableval[t] = slot[a+1] end
350 end,
351
352 CLOSE = empty,
353
354 CLOSURE = function(st, slot, pc, a, b, c)
355 slot[a] = empty
356 if st.noclose then
357 local nup = jutil.closurenup(st.func, b)
358 for i=pc+1,pc+nup do
359 local op = bytecode(st.func, i)
360 if op == "MOVE" then
361 st.noclose = false
362 return
363 end
364 end
365 end
366 end,
367
368 VARARG = function(st, slot, pc, a, b, c)
369 local params = st.stats.params
370 for i=1,b do slot[a+i-1] = st[params+i] end
371 end,
372}
373
374-- Generate some hints for the compiler backend.
375local function optimize(st)
376 -- Deoptimization is simple: just don't generate any hints. :-)
377 if st.deopt then return end
378
379 local func = st.func
380 local stats = jutil.stats(func)
381 if not stats then return jutil.status.COMPILER_ERROR end -- Eh?
382
383 -- Check limits.
384 if stats.bytecodes > LIMITS.bytecodes or
385 stats.stackslots > LIMITS.stackslots or
386 stats.params > LIMITS.params or
387 stats.consts > LIMITS.consts or
388 stats.subs > LIMITS.subs then
389 return jutil.status.TOOLARGE
390 end
391
392 -- Mark live instructions (live[pc]) and branch targets (live[-pc]).
393 local live = marklive(func)
394
395 -- Handlers need access to some temporary state fields.
396 st.noclose = true
397 st.stats = stats
398 st.live = live
399 st.tableval = { [stats.env] = empty } -- Guess: unknown globals are functions.
400
401 -- Initialize slots with argument hints and constants.
402 local slot = {}
403 for i=1,stats.params do slot[i-1] = st[i] end
404 for i=-1,-256,-1 do -- No need to copy non-RK-able consts.
405 local k, ok = const(func, i)
406 if not ok then break end
407 slot[i] = k
408 end
409
410 -- Step through all live instructions, update slots and add hints.
411 for pc=1,stats.bytecodes do
412 if live[pc] then
413 local op, a, b, c, test = bytecode(func, pc)
414 handler[op](st, slot, pc, a, b, c, op)
415 else
416 st[pc+hints.COMBINE] = false -- Dead instruction hint.
417 end
418 end
419
420 -- Update function hints.
421 if st.noclose then st[fhints.NOCLOSE] = true end
422
423 -- Clear temporary state fields.
424 st.noclose = nil
425 st.stats = nil
426 st.live = nil
427 st.tableval = nil
428end
429
430
431-- Active flags.
432local active, active_opt_inline
433
434-- Handler for compiler pipeline.
435local function h_opt(st)
436 if optlevel <= 0 then return end
437 local ok, err = pcall(optimize, st)
438 if not ok then
439 io.stderr:write("\nERROR: jit.opt disabled: ", err, "\n")
440 jit.attach(h_opt) -- Better turn ourselves off after a failure.
441 active = nil
442 else
443 if err then return err end
444 end
445end
446
447-- Load add-on module.
448local function loadaddon(opt)
449 local name, val = string.match(opt, "^(.-)=(.*)$") -- Strip value.
450 if not name then name = opt end
451 name = "jit.opt_"..name
452 local ok, mod = pcall(require, name)
453 if not ok then
454 -- Return error if not installed, but propagate other errors.
455 if string.sub(mod, 1, 7) ~= "module " then error(mod, 0) end
456 return "optimizer add-on module "..name.." not found"
457 end
458 mod.start(val)
459end
460
461-- Attach optimizer and set optimizer level or load add-on module.
462local function setlevel_(opt)
463 -- Easier to always attach the optimizer (even for -O0).
464 if not active then
465 jit.attach(h_opt, PRIORITY)
466 active = true
467 end
468
469 -- Parse -O<level> or -O<name[=value]>.
470 if opt == nil or opt == "" then
471 optlevel = OPTLEVEL
472 else
473 local level = tonumber(opt) -- Numeric level?
474 if level then
475 if level < 0 or level % 1 ~= 0 then
476 error("bad optimizer level", 0)
477 end
478 optlevel = level
479 else
480 if optlevel == -1 then optlevel = OPTLEVEL end
481 local err = loadaddon(opt)
482 if err then error(err, 0) end
483 end
484 end
485
486 -- Load add-on module for inlining functions for -O2 and above.
487 if not active_opt_inline and optlevel >= 2 then
488 loadaddon("inline") -- Be silent if not installed.
489 active_opt_inline = true -- Try this only once.
490 end
491end
492
493
494-- Public module functions.
495module(...)
496
497-- Callback to allow attaching a call hinter. Used by jit.opt_inline.
498function attach_callhint(f)
499 callhint = f
500end
501
502function getlevel()
503 return optlevel
504end
505
506setlevel = setlevel_
507start = setlevel_ -- For -O command line option.
508
generated by cgit v1.1 at 2024-07-01 04:48:46 +0000