Recently I was benchmarking the generated code efficiency for my C compiler\nantcc, and I noticed something concerning in a simple Lua benchmark:
\nbenchmark opt runtime\n lua 1.048s\n lua -O1 1.077s\n lua -O2 1.410sThe "optimized" builds were actually slower. Now, my compiler doesn't implement\nmany optimizations at the moment so I wouldn't expect a huge improvement, but\nbeing 1.4x slower should definitely not happen.<sup>[1]</sup> One of the optimizations\nthat antcc does have is inlining, which generally speaking is one of the most\nimpactful compiler optimizations and it usually improves benchmarks all around.
\nSo my first thought was, okay my inlining heuristics and thresholds are very simple and not really tuned, so perhaps it's being too aggressive and blowing up the code size, leading to very bad instruction cache thrashing. If I disabled inlining, the pessimization seemed to go away, which could support that theory. That's not a very satisfactory explanation though, and I would like to fix it, so I looked into it more.
\nThe main culprit was in the function luaV_execute, whose code blew up to\n~43KB with -O2, ~2.4x bigger than the -O1 build. Now, this function\nis the main bytecode interpreter loop for the Lua VM, and these are one of the\nworst kinds of functions for a compiler to deal with: it's a huge function with\na hot loop, many cases/control flow branches, distinct hot/cold paths nested in\nthe graph where a wrong optimizer or register-allocation decision can pessimize\nthe whole loop, etc...<sup>[2]</sup> So the baseline function is a tricky one, but it\ndoesn't explain this.
Tweaking the inlining thresholds didn't seem to help: either few things got\ninlined (like -O1) and binary size & performance stayed roughly the same, or\nsmall functions start getting inlined and the pessimization happens. In\nparticular, these functions were getting inlined (some in multiple instances):\nfloatforloop, lessequalothers, lessthanothers, luaV_idiv, luaV_mod,\nluaV_modf, luaV_shiftl, luaV_tointegerns, plus some of their respective\ncallees. In the Lua source code link above you can see those are all pretty\nsmall simple functions.
Looking at the final codegen is not that helpful, but examining the IR<sup>[3]</sup>\nrevealed something interesting: after all optimizations, the -O2 IR was only\n11% bigger than -O1. How could that be amplified to a 2.4x difference in\nthe binary?
\nThe final passes that run after optimizations and before code generation are\ninstruction selection and register allocation. Instruction selection\nmostly concerns itself with ensuring instruction operands are ready to be\nlowered into machine code, but keeps temporaries as virtual registers. For\nexample, for x86-64, it models memory operands and will turn a sequence of IR\ninstructions like:
\n;; int *ptr, res;\ni64 %t2 = shl %index, 2\nptr %t3 = add %ptr, %t2\n;; res = ptr[index]\ni32 %res = loads32 %t3into
\ni32 %res = loads32 addr [%ptr + %index * 4]\nIt does other things like introducing register constraints for certain operations, but anyway because it only expands into small sequences of instructions like this, it couldn't be the cause.
Register allocation is the process of mapping virtual temporaries to the target architecture's physical registers. For the previous snippet, that might result in
\ni32 RAX = loads32 addr [RSI + RDX * 4]\nwhich is compiled to the x86 instruction mov eax, DWORD PTR [rsi + rdx * 4].
The problem is that there are infinite virtual temporaries but a small number of registers,\nso you have to choose which variables get which registers and when there are not enough\nregisters for all of them, some of them have to go on the stack, which is called spilling.
\nMost operations require values to be in registers, so spilled variables often have to be moved back and forth between registers. Or even worse, they might have to be moved between two different stack slots in some situations.
\nantcc has a basic implementation of linear scan regalloc. If there is\na lot of register pressure and many temporaries get spilled, potentially a lot\nof instructions can be created just to shuffle values between stack and\nregisters.
\nAnd indeed, comparing relative IR size increase before and after regalloc at -O2, the +11%\ndifference was turning into +70% blowup after regalloc... looking at the disassembly,\n>40% of instructions in luaV_execute were just stack⇄register movs. That's really bad,\nsomething being inlined must be resulting in this dreadful register pressure and spilling,\nbut it's not obvious what.
So let's examine the pre-regalloc IR:
\n<< Before regalloc >>\nfunction luaV_execute : void(struct lua_State *, struct CallInfo *)\nabi: (RDI, RSI)\n ....\n ptr %4613 = add %0, 56\n ptr %5340 = add %0, 40\n b @2\n @2: ; preds: @1, @892 ; loop depth: 1\n i64 %4489 = phi @1 undef, @892 %3124\n i64 %3030 = phi @1 undef, @892 %3065\n i64 %4636 = phi @1 undef, @892 %2287\n i64 %4764 = phi @1 undef, @892 %3869\n i64 %2874 = phi @1 undef, @892 %3929\n i64 %2694 = phi @1 undef, @892 %3981\n i64 %4872 = phi @1 undef, @892 %3804\n i64 %2297 = phi @1 undef, @892 %3497\n i64 %5062 = phi @1 undef, @892 %3158\n i64 %2208 = phi @1 undef, @892 %3145\n i64 %2161 = phi @1 undef, @892 %4191\n i64 %5275 = phi @1 undef, @892 %4225\n i64 %5290 = phi @1 undef, @892 %4252\n i64 %1791 = phi @1 undef, @892 %4370\n i64 %3813 = phi @1 undef, @892 %3195\n i64 %3807 = phi @1 undef, @892 %4403\n ....Oh. That looks strange.
\nMy compiler like most modern backends uses a Static Single-Assignment representation.\nIn this form, straight-line code such as (I'm using C-like pseudocode to simplify):
\nx = a + b\nx = x + y # reassigning x\nuse(x)Becomes:
\nx1 = a + b\nx2 = x1 + y # fresh definition\nuse(x2)That is, there are no variable mutation instructions. The reason this representation is great for compilers is that it simplifies all kinds of data-flow analysis and permits some more powerful optimizations than the non-SSA counterpart.
\nWith control flow, data flow merges are explicit in the IR:
\nif (cond) {\n x = a + 1\n} else {\n x = b - 1\n}\nuse(x)In SSA form is represented as:
\nif (cond) B0: {\n x1 = a + 1\n} else B1: {\n x2 = b - 1\n}\nx3 = phi(B0: x1, B1: x2)\nuse(x3)This magic "phi" instruction<sup>[4]</sup> has as its result the value of x1 or x2 depending on which\ncontrol flow branch was taken. Same approach can be applied for variables modified in loops:
i = 0\nwhile (cond) {\n use(i)\n i += 1\n}in SSA:
\ni0 = 0\nEntry: while (cond) {\n LoopBegin:\n i_l = phi(Entry: i0, LoopEnd: i_n)\n use(i_l)\n i_n = i_l + 1\n LoopEnd:\n}Textually, it looks like the phi function references i_n before its definition, but\nimportantly that value is only taken in the loop back-edge (LoopEnd -> LoopBegin),\nand at that point the value of i_n is available.
A key thing to realize here is that this i_l temporary, being a loop phi, is live\nacross the whole loop, since its value is used to compute the next iteration.
Going back to that IR dump from Lua:
\n@2: ; preds: @1, @892 ; loop depth: 1\n i64 %4489 = phi @1 undef, @892 %3124\n i64 %3030 = phi @1 undef, @892 %3065\n ...Ignore the undefs for now, and notice the ; preds line indicating the\npredecessors of that block: @1, the beginning of the function, and @892,\nhundreds of blocks later: the end of the main interpreter loop. Meaning, we\nhave 16 phis that are live across the whole loop. This is what is creating a\nlot of register pressure, wrecking register allocation and resulting in that\nbig code size blowup from stack spilling traffic. So, what are these phis,\nwhere do they come from, and why the undefs...
C programs don't start in SSA form, so they have to go through a transformation pass. I borrowed the terminology and design from clang/LLVM in my compiler:
\nVariables always start as virtual stack slots, defined with an alloca pseudo-instruction.<sup>[5]</sup> - Since local variables in C can have their address taken<sup>[6]</sup> , this
directly models the C abstract machine's definition ofautomatic variables : a physical addressable stack slot that can be read from\nor written to.
load instructions, and writes turn intostore instructions.Later, the mem2reg pass collects stackalloca s whose address
does not escape (meaning they are only used for direct reads and writes\nthat the compiler can observe), and "promotes" them into SSA temporaries,\ninserting phi instructions where necessary.
So C code like:
\nint x;\nx = foo();\n...\nif (x < 0) { x = -x; }\nreturn x;Initially generates an IR that looks like:
\n@1:\n ptr %x = alloca 4 bytes\n i32 %t1 = call foo()\n store i32 %x, %t1\n ...\n i32 %t2 = load i32 %x\n bool %cond = lth %t2, 0\n br %cond, true -> @2, false -> @3\n@2:\n i32 %t3 = load i32 %x\n i32 %t4 = neg %t3\n store i32 %x, %t4\n b @3\n@3:\n i32 %t5 = load i32 %x\n ret %t5And mem2reg turns it to:
\n@1:\n i32 %x1 = call foo()\n ...\n bool %cond = lth %x1, 0\n br %cond, true -> @2, false -> @3\n@2:\n i32 %x2 = neg %x1\n b @3\n@3:\n i32 %x3 = phi @1 %x1, @2 %x2\n ret %x3I'm glossing over the trickiest part of this, which is knowing when and where\nto insert these phi instructions in the general case. There's basically two\nalgorithms to do it, and the one I'm using is from the paper "Simple and\nEfficient Construction of SSA Form (Braun et al, 2013)". The gist of\nit is: walk the control-flow graph (CFG) in reverse post-order (RPO); when you\nsee a write, memoize the current definition keyed by the block; when you see a read,\nlook for that definition or query the predecessors' definitions recursively and\ninsert phis when that lookup finds distinct definitions. Loops are trickier:\nbecause the back-edge predecessors haven't been visited yet, you have to insert\na provisional phi and resolve it later.
\nSomething about C that almost every language that came after it removed as a Bad Idea is the ability to leave variables uninitialized. For example:
\nint x;\nif (foo()) {\n int y = bar();\n x = y;\n}\nuse(x);After the control flow merge, x is phi(uninitialized, y). That is what\nthe undef in my IR is. The way it's introduced in my mem2reg is that if the\nrecursive "read current definition" function reaches all the way to the\nbeginning of the function without finding a definition, it gives it undef.\n(Later on, moves and operations on undef can be effectively optimized away.)
So was the Lua interpreter reading uninitialized variables? Well, no. Look at some of the affected code from the interpreter function:
\n vmcase(OP_SHRI) {\n TValue *rb = vRB(i);\n int ic = GETARG_sC(i);\n lua_Integer ib;\n if (tointegerns(rb, &ib)) {\n pc++; setivalue(s2v(ra), luaV_shiftl(ib, -ic));\n }\n vmbreak;\n }\n // several other instructions follow that same templateThe key is the tointegerns macro, which in turn calls the function luaV_tointegerns:
int luaV_tointegerns (const TValue *obj, lua_Integer *p, F2Imod mode) {\n if (ttisfloat(obj))\n return luaV_flttointeger(fltvalue(obj), p, mode); // <- this gets inlined\n else if (ttisinteger(obj)) {\n *p = ivalue(obj);\n return 1;\n }\n else\n return 0;\n}In -O2, this function and luaV_flttointeger get inlined, resulting in an\nexpansion like this (simplified):
vmcase(OP_SHRI) {\n ...\n lua_Integer ib; // <--- declaration\n int tointegerns_ret;\n if (ttisinteger(rb)) {\n ib = ivalue(rb); // <--- write\n tointegerns_ret = 1;\n } else if (ttisfloat(rb)) {\n ...\n ib = (lua_Integer)fvalue(f); // <--- write\n tointegerns_ret = 1;\n } else {\n tointegerns_ret = 0;\n }\n if (tointegerns_ret) {\n ... (use ib)\n }\n vmbreak;\n }mem2reg is always ran after every inlining pass. The undef in question\ncomes from the variable ib which I've marked. You can see that the local\nvariable is initialized in every path where the inlined function returns 1,\nbut mem2reg cannot correlate that with the later if (tointegerns_ret) guard,\nso it sees a possibly uninitialized read.
But that does not tell the whole story! It explains the undef, but not why\nthe phi is live across the whole loop. After all, this local is scoped to a\nblock inside a branch of the loop, it does not live across loop iterations...
Eventually I figured out the root cause: I was treating the idea of "variables\nstart as uninitialized" too literally in mem2reg. When it encountered an\nalloca, it didn't give it a definition for the current block. This sounds\ncorrect, and the recursive lookup in the algorithm terminates at the function\nentry with an undef. But recall the catch with loops being that when you\nencounter a backedge, you don't know if there's a later definition, because you\nhaven't visited the whole loop yet, so you insert a provisional phi...
In essence, my mem2reg was behaving as if code like:
\nint foo() {\n while (...) {\n int x;\n if (...) {\n x = bar();\n }\n use(x);\n }\n}was actually
\nint foo() {\n int x;\n while (...) {\n if (...) {\n x = bar();\n }\n use(x);\n }\n}In the 2nd function, the value of x is kept across iterations, whereas in the\n1st, the value of x is a 'fresh' uninitialized every time the if branch is\nnot taken... This is not a miscompilation: as far as C is concerned, this is\nfine because uninitialized variables' values are not legally usable anyway. And\nif you frame it in terms of stack-allocated variables, it's a sensible\napproach: the slot for x is fixed for the whole function and doesn't get\nreset between loop iterations, so it keeps the previous iteration's whatever\nit was and it doesn't matter. But the problem is that in the context of SSA\nform, this generates something like:
while (...) {\n %x = phi(undef, %x2)\n if (...) {\n %x1 = bar();\n }\n %x2 = phi(%x, %x1)\n use(%x2);\n}And it is these loop phis that result in the pathological register allocation. The fix was one line:
\n--- a/src/ir_mem2reg.c\n+++ b/src/ir_mem2reg.c\n@@ -244,6 +244,8 @@ mem2reg(Function *fn) {\n v->cls = k;\n v->i = var;\n sb.vars[var] = v;\n+ v->curdefs[blk->id] = UNDREF;\n } else {\n sb.vars[var] = DEAD;\n }Initializing the var as undefined (a nice oxymoron) at the place of the\nalloca ensures that the recursive lookup doesn't cross loop backedges and\ninsert phis in the loop header. This is enough to fix this case, and that\nchange made the mysterious pessimization disappear.
This problem can still bite for C code that is old-style declaring all\nvariables at the top of the function. It's possible to fix this general case by\nusing Tarjan's algorithm to find the graph SCCs of the phi data-flow to\ndetect cycles, and making use of these undef semantics when classifying\nphis as redundant; but I haven't implemented that yet.
\nJump threading an inlined function used directly as a branch condition, or more\ngenerally SSA-aware phi jump threading, could've also fixed the branch\ncorrelation issue that led to mem2reg not seeing the dominating write of\nthose variables and introducing undefs.
I made use of AI agents to help debug this issue. It saved me a lot of time in investigating, filtering through disassemblies and IR dumps, running the compiler with different inlining thresholds and measuring, etc; but it was not good at trying to find the root cause. It proposed probably around 10 convoluted "fixes" before I eventually arrived at the conclusion myself. Still <$1 well spent for the sake of reducing tedium.
\nLua 5.4.7, bench.lua, AMD Ryzen 5 5600G. Take\nthese with a grain of salt.
\nPre-fix:
\nantcc was worse than even tcc, but that's mainly because my frontend was lowering switch statements to linear if-else chains. I implemented a simple binary search codegen, which was one of those things that I just hadn't gotten around to yet; and a few other minor optimizations; after this fix.
\nCurrent numbers:
\nDo note that antcc performs mem2reg by default when passed no optimization\nflags, unlike gcc. It might seem counterintuitive, but from my testing, running\nmem2reg improves compile times too; presumably due to the reduced number of\nstack store/load instructions for the backend to churn through.
And compile times:
\nI omitted the bars for clang because they are all very similar to gcc.
\nThe only difference between -O1 and -O2 is in inlining thresholds and -O2 running some optimization passes more than once. ↩
\nThis is why LuaJIT's interpreter in hand-written assembly beats almost every other bytecode interpreter, and it's not just about the while-switch loop↩
\nIntermediate representation ↩
\nvariously known as phi function, φ, /faɪ/, /fi/, phony instruction ↩
\nNot to be confused with the dynamic alloca() function.↩
The register storage class exists, but it doesn't really matter in\nmodern architectures so you (almost) never see it used.↩