... extraordinarily large (60-80k lines) ...
... dying with an out-of-memory error.
How many symbols does the sub have? Please set a breakpoint at imcc/reg_alloc.c:468 and inspect:
n_symbols
(or just create a debug print statement there)
The interference_graph size is n_symbols * n_symbols * sizeof(a_pointer). This might already be too much.
2) There is a note in the source code that the interference graph could be done without the N x N graph array. Any hints welcome (Angel Faus!).
3) We don't rename registers (except when it comes to spilling). So when a symbol starts its life somewhere at the beginning of the subroutine and is used down to the end, it interfers with each other symbol in that range. One register is blocked permanently. When there are around 30 such long-ranged symbols, spilling starts, which means that the variable is stored into and fetched from a spill array.
This could be avoided, if the symbol is a lexical or a global variable. On each fetch of this variable it could get a fresh register. This currently depends on the source code:
foo = global "foo" # bad $P1234 = global "foo" # good - if each fetch increments the $P...
4) Proper register allocation depends on a correct life analysis of the symbol, which depends basically on 2 things:
4.1) the usage of the register in the opcode. Have a look at ops/*.ops:
op add(in PMC, in PMC)
The destination (left hand side) of add is a "in" register, the PMC has to exist beforehand as well as the source operand of course.
op find_lex(out PMC, in STR)
The destination PMC register is filled with the address of the lexical. It gets a new pointer there, the usage is written as "out". This means for the register allocator that the life range of this register starts here. Whatever was in that register is "dead".
But we have opcodes that silently have such an influence on the registers life range. These are mainly stack pop opcodes. Some of these opcodes are handled manually inside imcc, but not all. This leads to wrong or too long life ranges and to spilling stress.
There was a TODO item (posted on the list) to mark up all opcodes in the source to carry along their register usage. This is still badly required.
4.2) Basic blocks, life span of symbols inside these blocks and loop detection.
A basic block is a stream of opcodes that runs in one step without a branch and it isn't a branch target - no other opcode can jump inside such a basic block. If a symbol is used as "in" inside of such a block, it had to exist beforehand. Its life range is propagated down to the "previous" block. This is straight forward for branches but gets nasty with loops and subroutines.
The code in cfg.c is cluttered by exceptions that try to follow the control flow of stack-based subroutines ("bsr") and CPS subroutines. "invoke". This code needs cleaning up and I'm willing to eliminate support for old code that uses "bsr" and doesn't preserve registers. The main problem with "invoke" is that it doesn't carry a specific branch destination.
But anyway basic block detechtion should be ok. *But* its totally untested, which is bad. Any hints for testing it, patches, test frame work is really welcome.
Finally there is the loop detection, which is beyond my theoretical knowledge. Its totally untested too. The same TODO as above applies.
Any help is welcome.
leo
