diff options
Diffstat (limited to '')
-rw-r--r-- | libraries/LuaJIT-1.1.7/jit/opt.lua | 508 |
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. | ||
29 | local 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. | ||
33 | local 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. | ||
39 | local 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. | ||
48 | local jit = require("jit") | ||
49 | assert(jit.version_num == 10107, "LuaJIT core/library version mismatch") | ||
50 | local jutil = require("jit.util") | ||
51 | local type, rawget, next, pcall = type, rawget, next, pcall | ||
52 | local bytecode, const = jutil.bytecode, jutil.const | ||
53 | local hints, fhints = jutil.hints, jutil.fhints | ||
54 | local getmetatable = getmetatable | ||
55 | |||
56 | -- Turn compilation off for the whole module. LuaJIT would do that anyway. | ||
57 | jit.off(true, true) | ||
58 | |||
59 | -- Default optimizer level after loading. But -O runs setlevel(), too. | ||
60 | local optlevel = -1 | ||
61 | |||
62 | |||
63 | -- Use iterative path marking to mark live instructions and branch targets. | ||
64 | local 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 | ||
100 | end | ||
101 | |||
102 | |||
103 | -- Empty objects. | ||
104 | local function empty() end | ||
105 | |||
106 | -- Dummy function to set call hints. Replaced when jit.opt_inline is loaded. | ||
107 | local 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 | ||
110 | end | ||
111 | |||
112 | -- Set TYPE hint, but only for numbers, strings or tables. | ||
113 | local 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 | ||
118 | end | ||
119 | |||
120 | -- Set TYPE and TYPEKEY hints for table operations. | ||
121 | local 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 | ||
129 | end | ||
130 | |||
131 | -- Try to lookup a value. Guess the value or at least the value type. | ||
132 | local 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 | ||
150 | end | ||
151 | |||
152 | -- Check whether the previous instruction sets a const. | ||
153 | local 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 | ||
161 | end | ||
162 | |||
163 | -- Common handler for arithmetic and comparison opcodes. | ||
164 | local 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 | ||
183 | end | ||
184 | |||
185 | -- Common handler for TEST and TESTSET. | ||
186 | local 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] | ||
194 | end | ||
195 | |||
196 | -- Dispatch table for opcode handlers. | ||
197 | local 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. | ||
375 | local 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 | ||
428 | end | ||
429 | |||
430 | |||
431 | -- Active flags. | ||
432 | local active, active_opt_inline | ||
433 | |||
434 | -- Handler for compiler pipeline. | ||
435 | local 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 | ||
445 | end | ||
446 | |||
447 | -- Load add-on module. | ||
448 | local 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) | ||
459 | end | ||
460 | |||
461 | -- Attach optimizer and set optimizer level or load add-on module. | ||
462 | local 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 | ||
491 | end | ||
492 | |||
493 | |||
494 | -- Public module functions. | ||
495 | module(...) | ||
496 | |||
497 | -- Callback to allow attaching a call hinter. Used by jit.opt_inline. | ||
498 | function attach_callhint(f) | ||
499 | callhint = f | ||
500 | end | ||
501 | |||
502 | function getlevel() | ||
503 | return optlevel | ||
504 | end | ||
505 | |||
506 | setlevel = setlevel_ | ||
507 | start = setlevel_ -- For -O command line option. | ||
508 | |||