From f6aab3ec1f111cd8d968bdcb7ca800e93b819d24 Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Fri, 12 Jul 2019 11:38:42 -0300 Subject: First implementation of constant propagation Local constant variables initialized with compile-time constants are optimized away from the code. --- testes/code.lua | 89 +++++++++++++++++++++++++++++++++------------------ testes/constructs.lua | 24 ++++++++++++-- testes/locals.lua | 2 +- testes/math.lua | 16 +++++---- 4 files changed, 89 insertions(+), 42 deletions(-) (limited to 'testes') diff --git a/testes/code.lua b/testes/code.lua index 128ca2cb..49d682f8 100644 --- a/testes/code.lua +++ b/testes/code.lua @@ -7,6 +7,22 @@ if T==nil then end print "testing code generation and optimizations" +-- to test constant propagation +local k0 = 0 +local k1 = 1 +local k3 = 3 +local k6 = k3 + (k3 << k0) +local kFF0 = 0xFF0 +local k3_78 = 3.78 +local x, k3_78_4 = 10, k3_78 / 4 +assert(x == 10) + +local kx = "x" + +local kTrue = true +local kFalse = false + +local kNil = nil -- this code gave an error for the code checker do @@ -27,12 +43,12 @@ end local function foo () local a - a = 3; + a = k3; a = 0; a = 0.0; a = -7 + 7 - a = 3.78/4; a = 3.78/4 - a = -3.78/4; a = 3.78/4; a = -3.78/4 + a = k3_78/4; a = k3_78_4 + a = -k3_78/4; a = k3_78/4; a = -3.78/4 a = -3.79/4; a = 0.0; a = -0; - a = 3; a = 3.0; a = 3; a = 3.0 + a = k3; a = 3.0; a = 3; a = 3.0 end checkKlist(foo, {3.78/4, -3.78/4, -3.79/4}) @@ -86,10 +102,11 @@ end, 'CLOSURE', 'NEWTABLE', 'GETTABUP', 'CALL', 'SETLIST', 'CALL', 'RETURN') -- sequence of LOADNILs check(function () + local kNil = nil local a,b,c local d; local e; local f,g,h; - d = nil; d=nil; b=nil; a=nil; c=nil; + d = nil; d=nil; b=nil; a=kNil; c=nil; end, 'LOADNIL', 'RETURN0') check(function () @@ -109,7 +126,7 @@ check (function (a,b,c) return a end, 'RETURN1') -- infinite loops -check(function () while true do local a = -1 end end, +check(function () while kTrue do local a = -1 end end, 'LOADI', 'JMP', 'RETURN0') check(function () while 1 do local a = -1 end end, @@ -125,9 +142,9 @@ check(function (a,b,c,d) return a..b..c..d end, -- not check(function () return not not nil end, 'LOADBOOL', 'RETURN1') -check(function () return not not false end, 'LOADBOOL', 'RETURN1') +check(function () return not not kFalse end, 'LOADBOOL', 'RETURN1') check(function () return not not true end, 'LOADBOOL', 'RETURN1') -check(function () return not not 1 end, 'LOADBOOL', 'RETURN1') +check(function () return not not k3 end, 'LOADBOOL', 'RETURN1') -- direct access to locals check(function () @@ -144,7 +161,8 @@ end, -- direct access to constants check(function () local a,b - a.x = 3.2 + local c = kNil + a[kx] = 3.2 a.x = b a[b] = 'x' end, @@ -152,8 +170,9 @@ end, -- "get/set table" with numeric indices check(function (a) + local k255 = 255 a[1] = a[100] - a[255] = a[256] + a[k255] = a[256] a[256] = 5 end, 'GETI', 'SETI', @@ -170,7 +189,7 @@ end, check(function () local a,b - a[true] = false + a[kTrue] = false end, 'LOADNIL', 'LOADBOOL', 'SETTABLE', 'RETURN0') @@ -238,37 +257,39 @@ local function checkF (func, val) end checkF(function () return 0.0 end, 0.0) -checkI(function () return 0 end, 0) -checkI(function () return -0//1 end, 0) +checkI(function () return k0 end, 0) +checkI(function () return -k0//1 end, 0) checkK(function () return 3^-1 end, 1/3) checkK(function () return (1 + 1)^(50 + 50) end, 2^100) checkK(function () return (-2)^(31 - 2) end, -0x20000000 + 0.0) -checkF(function () return (-3^0 + 5) // 3.0 end, 1.0) -checkI(function () return -3 % 5 end, 2) +checkF(function () return (-k3^0 + 5) // 3.0 end, 1.0) +checkI(function () return -k3 % 5 end, 2) checkF(function () return -((2.0^8 + -(-1)) % 8)/2 * 4 - 3 end, -5.0) checkF(function () return -((2^8 + -(-1)) % 8)//2 * 4 - 3 end, -7.0) checkI(function () return 0xF0.0 | 0xCC.0 ~ 0xAA & 0xFD end, 0xF4) -checkI(function () return ~(~0xFF0 | 0xFF0) end, 0) +checkI(function () return ~(~kFF0 | kFF0) end, 0) checkI(function () return ~~-1024.0 end, -1024) -checkI(function () return ((100 << 6) << -4) >> 2 end, 100) +checkI(function () return ((100 << k6) << -4) >> 2 end, 100) -- borders around MAXARG_sBx ((((1 << 17) - 1) >> 1) == 65535) local a = 17; local sbx = ((1 << a) - 1) >> 1 -- avoid folding -checkI(function () return 65535 end, sbx) -checkI(function () return -65535 end, -sbx) -checkI(function () return 65536 end, sbx + 1) -checkK(function () return 65537 end, sbx + 2) -checkK(function () return -65536 end, -(sbx + 1)) +local border = 65535 +checkI(function () return border end, sbx) +checkI(function () return -border end, -sbx) +checkI(function () return border + 1 end, sbx + 1) +checkK(function () return border + 2 end, sbx + 2) +checkK(function () return -(border + 1) end, -(sbx + 1)) -checkF(function () return 65535.0 end, sbx + 0.0) -checkF(function () return -65535.0 end, -sbx + 0.0) -checkF(function () return 65536.0 end, (sbx + 1.0)) -checkK(function () return 65537.0 end, (sbx + 2.0)) -checkK(function () return -65536.0 end, -(sbx + 1.0)) +local border = 65535.0 +checkF(function () return border end, sbx + 0.0) +checkF(function () return -border end, -sbx + 0.0) +checkF(function () return border + 1 end, (sbx + 1.0)) +checkK(function () return border + 2 end, (sbx + 2.0)) +checkK(function () return -(border + 1) end, -(sbx + 1.0)) -- immediate operands -checkR(function (x) return x + 1 end, 10, 11, 'ADDI', 'RETURN1') +checkR(function (x) return x + k1 end, 10, 11, 'ADDI', 'RETURN1') checkR(function (x) return 128 + x end, 0.0, 128.0, 'ADDI', 'RETURN1') checkR(function (x) return x * -127 end, -1.0, 127.0, 'MULI', 'RETURN1') checkR(function (x) return 20 * x end, 2, 40, 'MULI', 'RETURN1') @@ -276,7 +297,7 @@ checkR(function (x) return x ^ -2 end, 2, 0.25, 'POWI', 'RETURN1') checkR(function (x) return x / 40 end, 40, 1.0, 'DIVI', 'RETURN1') checkR(function (x) return x // 1 end, 10.0, 10.0, 'IDIVI', 'RETURN1') checkR(function (x) return x % (100 - 10) end, 91, 1, 'MODI', 'RETURN1') -checkR(function (x) return 1 << x end, 3, 8, 'SHLI', 'RETURN1') +checkR(function (x) return k1 << x end, 3, 8, 'SHLI', 'RETURN1') checkR(function (x) return x << 2 end, 10, 40, 'SHRI', 'RETURN1') checkR(function (x) return x >> 2 end, 8, 2, 'SHRI', 'RETURN1') checkR(function (x) return x & 1 end, 9, 1, 'BANDK', 'RETURN1') @@ -295,7 +316,7 @@ checkR(function (x) return x % (100.0 - 10) end, 91, 1.0, 'MODK', 'RETURN1') -- no foldings (and immediate operands) check(function () return -0.0 end, 'LOADF', 'UNM', 'RETURN1') -check(function () return 3/0 end, 'LOADI', 'DIVI', 'RETURN1') +check(function () return k3/0 end, 'LOADI', 'DIVI', 'RETURN1') check(function () return 0%0 end, 'LOADI', 'MODI', 'RETURN1') check(function () return -4//0 end, 'LOADI', 'IDIVI', 'RETURN1') check(function (x) return x >> 2.0 end, 'LOADF', 'SHR', 'RETURN1') @@ -335,7 +356,7 @@ end, do -- tests for table access in upvalues local t - check(function () t.x = t.y end, 'GETTABUP', 'SETTABUP') + check(function () t[kx] = t.y end, 'GETTABUP', 'SETTABUP') check(function (a) t[a()] = t[a()] end, 'MOVE', 'CALL', 'GETUPVAL', 'MOVE', 'CALL', 'GETUPVAL', 'GETTABLE', 'SETTABLE') @@ -379,6 +400,12 @@ function (a) end ) +checkequal(function () return 6 or true or nil end, + function () return k6 or kTrue or kNil end) + +checkequal(function () return 6 and true or nil end, + function () return k6 and kTrue or kNil end) + print 'OK' diff --git a/testes/constructs.lua b/testes/constructs.lua index fe4db2cb..8a549e10 100644 --- a/testes/constructs.lua +++ b/testes/constructs.lua @@ -287,7 +287,7 @@ a,b = F(nil)==nil; assert(a == true and b == nil) ------------------------------------------------------------------ -- sometimes will be 0, sometimes will not... -_ENV.GLOB1 = math.floor(os.time()) % 2 +_ENV.GLOB1 = math.random(0, 1) -- basic expressions with their respective values local basiccases = { @@ -298,6 +298,26 @@ local basiccases = { {"(0==_ENV.GLOB1)", 0 == _ENV.GLOB1}, } +local prog + +if _ENV.GLOB1 == 0 then + basiccases[2][1] = "F" -- constant false + + prog = [[ + local F = false + if %s then IX = true end + return %s +]] +else + basiccases[4][1] = "k10" -- constant 10 + + prog = [[ + local k10 = 10 + if %s then IX = true end + return %s + ]] +end + print('testing short-circuit optimizations (' .. _ENV.GLOB1 .. ')') @@ -337,8 +357,6 @@ cases[1] = basiccases for i = 2, level do cases[i] = createcases(i) end print("+") -local prog = [[if %s then IX = true end; return %s]] - local i = 0 for n = 1, level do for _, v in pairs(cases[n]) do diff --git a/testes/locals.lua b/testes/locals.lua index 0de00a98..1b82dd7f 100644 --- a/testes/locals.lua +++ b/testes/locals.lua @@ -324,7 +324,7 @@ do -- errors due to non-closable values local function foo () - local x = 34 + local x = {} end local stat, msg = pcall(foo) assert(not stat and string.find(msg, "variable 'x'")) diff --git a/testes/math.lua b/testes/math.lua index c45a91ad..befce12e 100644 --- a/testes/math.lua +++ b/testes/math.lua @@ -270,7 +270,7 @@ else end do - local NaN = 0/0 + local NaN = 0/0 assert(not (NaN < 0)) assert(not (NaN > minint)) assert(not (NaN <= -9)) @@ -767,7 +767,8 @@ assert(a == '10' and b == '20') do print("testing -0 and NaN") - local mz, z = -0.0, 0.0 + local mz = -0.0 + local z = 0.0 assert(mz == z) assert(1/mz < 0 and 0 < 1/z) local a = {[mz] = 1} @@ -775,17 +776,18 @@ do a[z] = 2 assert(a[z] == 2 and a[mz] == 2) local inf = math.huge * 2 + 1 - mz, z = -1/inf, 1/inf + local mz = -1/inf + local z = 1/inf assert(mz == z) assert(1/mz < 0 and 0 < 1/z) - local NaN = inf - inf + local NaN = inf - inf assert(NaN ~= NaN) assert(not (NaN < NaN)) assert(not (NaN <= NaN)) assert(not (NaN > NaN)) assert(not (NaN >= NaN)) assert(not (0 < NaN) and not (NaN < 0)) - local NaN1 = 0/0 + local NaN1 = 0/0 assert(NaN ~= NaN1 and not (NaN <= NaN1) and not (NaN1 <= NaN)) local a = {} assert(not pcall(rawset, a, NaN, 1)) @@ -814,8 +816,8 @@ end -- the first call after seed 1007 should return 0x7a7040a5a323c9d6 do -- all computations assume at most 32-bit integers - local h = 0x7a7040a5 -- higher half - local l = 0xa323c9d6 -- lower half + local h = 0x7a7040a5 -- higher half + local l = 0xa323c9d6 -- lower half math.randomseed(1007) -- get the low 'intbits' of the 64-bit expected result -- cgit v1.2.3-55-g6feb