Source Optimizer

wiki

Description

Inlining is a form of partial evaluation [1].

Code

The code requires the [Metalua 0.5] (development branch).

It consists of these files:

• [dmlib/sourceoptimizer.mlua] - library module (in Metalua)
• [sourceoptimize.lua] - command line utility
• [test_sourceoptimizer.lua] - test suite

Quick Start

Download tar file from http://github.com/fab13n/metalua/tree/0.5-branch .

tar xzvf fab13n-metalua-28e8e1037ab33d96c123667f4c3fc94b5aca83bc.tar.gz
mv fab13n-metalua-28e8e1037ab33d96c123667f4c3fc94b5aca83bc metalua
cd metalua && make

Download sourceoptimizer.mlua and place in metalua/build/lib/dmlib .
Download sourceoptimize.lua and place in metalua/ .
Download fib.lua example and place in metalua/ .

./build/bin/metalua sourceoptimize.lua fib.lua
# or
./build/bin/metalua sourceoptimize.lua fib.lua  | lua -

Examples

This is a basic example:

-- input:
local y=-1
local function square(x) return x*x end
local function g(x) return x >= 0 and square(square(x))+1 or 1 end
while (function() y = g(y)^(1/4) return y < 2 end)() do
  print(y)
end

-- output:
local y = - 1
while 1 do
   local __v13x = y
   local __v10 = 0 <= __v13x
   if __v10 then
      local __v12x = __v13x
      local __v14x = __v12x * __v12x
      __v10 = __v14x * __v14x + 1
   end
   local __v11 = __v10
   if not __v11 then
      __v11 = 1
   end
   y = __v11 ^ (1 / 4)
   if not (y < 2) then
      break
   end
   print (y)
end

Examples of inlining some of the Lua examples (after adding "local" before function names, which is required for inlining) are below:

• [fib.lua] [fib-out.lua]
• [sort.lua] [sort-out.lua]
• [bisect.lua] [bisect-out.lua]
• [sieve.lua] [sieve-out.lua]
• [license.html]

Capability Notes

The code will inline anonymous functions that are immediately evaluated:

x=(function(x) return x*x end)(y())
--> local __v1x=y() x=__v1x*__v1x

and local functions that are "constant" (function variable never modified):

local function square(x) return x*x end; x=square(y())
--> local __v1x=y() x=__v1x*__v1x

It eliminates dead functions, such as functions that are fully inlined (as above). It correctly performs transformations to convert expressions into statements:

x = y or (function(x)z=1 return x*x end)(w)
--> local __v2=y if not __v2 then local __v1x=w z=1 __v2=__v1x*__v1x end x=__v2

if (function()x=x+1 return x end)() then f()
elseif (function()y=y+1 return y end)() then g()
else h() end
--> x=x+1 if x then f()else y=y+1 if y then g()else h()end end

Functions that use setfenv and stack levels with the debug library might not inline correctly. This potentially could occur on access to any global variable:

local function f() local _ = x end
f()

In theory we should not inline the above function since the access to global variable x "might" trigger a metatable on the global environment, which in turn might alter the environment of f, so inlining f would alter the environment of f's caller. (Environments will not be an issue anymore in LuaFiveTwo, but some debug functions still utilize stack levels.) Ideally, the translator should be extended to support pragmas inside Lua comments that define how aggressive we want to inline:

--!inline
local function f() local _ = x end
f()

This could be on a per-function basis or can be a more global default setting in the file. (See luaanalyze in LuaFish for suggested syntax design.)

See source code of sourceoptimizer.mlua for further details.

Limitations

Warning: may not work correctly for odd cases where inlined function uses setfenv or debug functions that utilize stack levels (see above). The getfenv/setfenv issue will be less significant in LuaFiveTwo.

Possible Applications

• Avoid manually inlining functions for optimization (OptimisationTips).
• Refactoring
• Optimize code before sending to LuaToCee.
• Optimize automatically generated Lua code from source preprocessors, including MetaLua and token filters. (Use native Lua byte code generator to expand Metalua `Stat nodes?)
• Does LuaJIT 2.x do something similar? LuaList:2009-02/msg00411.html

Possible Extensions

• Replace "for i,v in ipairs(t) do" with "local __t=t; for i=1,#__t do local v=__t[i]" (typically more efficient). Only do if ipairs not redefined in file. But allow "local ipairs = ipairs".
• Remove dead code, e.g. "if false then ... end"
• Add option to preserve line numbers to the reduce impact on debugging information. LuaList:2010-06/msg00311.html

Author

DavidManura