Eliminating unused code (Compiler/language design)

[AndrewAPrice]

I wrote up a simple example that has many potential optimization cases:

Code: Select all

var i = 0;
var somethingNotPure = function(b) { i += b; };
var somethingPure = function(abc) { return abc; };

var f = function(a) {
	var q = 2;
	var one = 3 - 2;
	var b = somethingPure(a + one) * q;
	var c = 0;

	for(var i = 0; i < 10; i++) {
		b += somethingPure(a + one);
		somethingNotPure(b);
		c += somethingPure(q);
	}

	return b;
};

f(100);

somethingNotPure has side effects (it modifies i), while somethingPure does not. 'c' is never used, so 'c += somethingPure(q);' should be optimized away.

That's 176 instructions, unoptimized, in SSA form, here: http://pastebin.com/yAJeaTSQ The push/parameter instructions indicate variables coming in or transferring to another basic block (my form of the SSA phi symbol) - also used for calling functions. Most of these should be optimized away, as value that aren't needed shouldn't be passed around. 'var one = 3 - 2;' can be turned into a constant and does not need to be passed around either.

I've never tackled SSA optimization before, so I feel like I'm jumping into the deep end of the pool to learn how to swim.

My plan is to optimize on a per-function basis, marking every SSA instruction as 'unused', then iterate, linearly over each basic block and instruction, and when I encounter either: a return, a memory write, or a non-pure function call, I will mark each parameter, which in turn will either a) recursively mark it's dependencies, or b) propagate up a constant value.

[Rusky]

LLVM has a good set of SSA optimization passes you could look at for inspiration: http://llvm.org/docs/Passes.html Some interesting ones are mem2reg, reassociate, instcombine, scalarrepl, simplifycfg, constprop, and dce.

[AndrewAPrice]

Thanks for the link Ruskey.

An update on progress:

I have constant folding* and detecting used instructions by finding rooted instructions and marking dependencies backwards from there (I printed all the SSA instructions with '*' next to the ones that are used, and if an instruction outputs a known type it it's printed with that type before the column) - results here: http://pastebin.com/FEyt49kH

* Constants are easy to propagate through basic blocks because execution is linear. I also propagate constants by matching "param x" with the push instructions at the end of the callees.

There is a special case that fails when propagating constants across loops for example:

Code: Select all

var a = 10;
while(true) {
   doSomething(a);
}

I push 'a' back on the stack when looping when I generate SSA because we're jumping between basic blocks, so the stack matches when I enter the while loop. For example:

Code: Select all

BB0
0: unsigned 10
1: push [0]

BB1: entry BB0, BB2
0: param 0
1: doSomething [0]
2: push [0]

BB2: param [0]
0: param 0
1: jump BB1
2: push [0]

Now I would like this to be optimized to:

Code: Select all

BB0

BB1: entry BB0, BB2
0: unsigned 10
1: doSomething [0]

BB2: param [0]
0: jump BB1

When I try walking backwards to see if I can propagate 'a' through at a constant, I get stuck in a recursive loop because BB1/0: param 0 evaluates to either BB0:1 or BB2:2, and following BB2 enters me into an unevaluatable loop. It's just a matter of me thinking out an algorithm that doesn't get stuck in an infinite loop.

I still need to clean up the output and remove unused instructions (I just merely mark the needed instructions, but need to remove them), evaluate conditional jumps if they're constants, and merge basic blocks - these should be trivial once I work on the recursive problem.

Here's my SSA optimization code so far, it's very gritty and needs to be cleaned up: https://github.com/MessiahAndrw/Perception/blob/master/turkey/ssa_optimizer.cpp

[AndrewAPrice]

I solved the infinite cycle problem. I scan the graph following push/parameter pairs (marking parameters I've already encountered to avoid cycles), building up an array of 'end points', I then evaluate the end points, and if they're constant, fold the constant value into the original parameter instruction. This works very well.

The optimized SSA was 176 instructions, it is now only 76 instructions: http://pastebin.com/TT4zLT67 That's only 43%! If I eliminate the push/parameters (since they're not real instructions, only meta-instructions that are not going to be compiled) there are only 36 real instructions.

Still to do - merge basic blocks together (BB5 can be merged into BB4 since we eliminated the function call and BB5 has no entry points), and fold constant conditional jumps into unconditional jumps.