Eliminating unused code (Compiler/language design)

[AndrewAPrice]

I've been thinking about single static assignment form in preparation for writing a JIT compiler in my virtual machine. One of the very nice things about SSA form is the ability to detect unused variables.

For example - in psuedo code:

Code: Select all

var a = 10;
a = 5;
return a;

In SSA form this could be written as:

Code: Select all

a1 = 10
a2 = 5
return a2

Now, because we can see a1 is not used, we can eliminate it, reducing the function to:

Code: Select all

a2 = 5
return a2

(We could take this one step further and detect a2 is a constant and just "return 5".)

In the following code:

Code: Select all

var a = randomNumber();
a = 5;
return a;

We can detect that the result of our function call to randomNumber() is assigned to a (a1 in SSA form) but because that value is never used, we can eliminate it the call to randomNumber().

But how do we now if it is safe to eliminate a function call? Another example with objects would be this:

Code: Select all

var random = new RandomNumberGenerator();
a = random.randomNumber();
a = 5;
return a;

In SSA form:

Code: Select all

random1 = new RandomNumberGenerator()
a1 = random1.randomNumber()
a2 = 5
return a2

Working backwards, we can see that the value of a1 is never referenced, so we eliminate it:

Code: Select all

random1 = new object
a2 = 5
return a2

Now, random1 is never referenced, so we can eliminate it:

Code: Select all

a2 = 5
return a2

In that example, we were able to remove the construction of an object and a function call, because we knew we weren't going to use the result.

However - what if the function has side effects? For example:

Code: Select all

var file = new File("abc.txt");
var a = file.write("hello");
a = 5;
return a;

In SSA form:

Code: Select all

file1 = new File("abc.txt")
a1 = file.write("hello")
a2 = 5
return a2

Since a1 is never used, we'd eliminate it:

Code: Select all

file1 = new File("abc.txt")
a2 = 5
return a2

Now that file1 is not used, we'd eliminate it too:

Code: Select all

a2 = 5
return a2

However, file.write has side-effects. It has to perform something, even if we do not use the value it returned.

Imagine this example:

Code: Select all

var file = new File("abc.txt");
var error = file1.write("hello");
// check here
error = file1.write("hello");
// check here

in SSA form:

Code: Select all

file1 = new File("abc.txt")
error1 = file1.write("hello")
error2 = file1.write("hello")

We see that error1 and error2 have the same value, so rather than call it twice, one can reference the other:

Code: Select all

file1 = new File("abc.txt")
error1 = file1.write("hello")
error2 = error1

This also opens a whole can of worms on figuring out if functions can be rearranged, if duplicate code can be reused, etc.

I'm thinking either:

• Assume all function calls have side-effects, and never eliminate them. At best we may remove the assignment but never the function call:
  

  Code: Select all

  file1 = new File("abc.txt")
  a1 = file.write("hello")
  a2 = 5
  return a2

  May be reduced to:

  Code: Select all

  file1 = new File("abc.txt")
  file.write("hello")
  a2 = 5
  return a2

  The assignment "a1 =" was eliminated, but the function call is still there.
• Have some language feature to distinguish between functions with side-effects and functional functions without side-effects. In a static language it may be possible for the compiler to automatically detect this, but this would be much harder in a dynamic language - as functions are first class types and we don't exactly know the function we are calling at compile time. However, a programmer usually may have a good idea if a function has side-effects and if it may be removed or called out of order, so we could add syntax to tell the compiler that the function call is functional.
  
  For example:

  Code: Select all

  var a = cos#(b); // the # tells the compiler this is a functional function that may be eliminated
  var c = sqrt#(d);
  var e = file.write("abc"); // no #, cannot be eliminated

If you're curious, I'm converting my byte-code to two-address code for SSA analysis:
https://github.com/MessiahAndrw/Percept ... ntation.md

Being SSA, the destination is literally the instruction itself, e.g.:

Code: Select all

0x000 Float 5.0
0x001 Float 8.0
0x002 Add 0x000 0x001 ; 5 + 8 = 13
0x003 Float 7.1
0x004 Add 0x002 0x003 ; 13 + 7.1 = 20.1
0x005 Return 0x004 ; returns 20.1

[Brendan]

Hi,

One of the very nice things about SSA form is the ability to detect unused variables.

Yes, and no. The main difficulty is control flow (branches, loops, etc) - something is unused if it's not used in any possible path. This mostly means propagating information backwards (from one step to all preceding steps) in a directed graph.

I'm thinking either:

• Assume all function calls have side-effects...
• Have some language feature to distinguish between functions with side-effects and functional functions without side-effects...

It's "relatively trivial" for a compiler to determine if a function has side effects or not: a function has side-effects if it contains reads or writes to global memory or calls a function with side effects.

Because it's "relatively trivial" for a compiler to determine if a function has side effects or not; a compiler is bad if:

• it assumes all function calls have side-effects (preventing some significant optimisations), or
• it has some language feature that forces programmers to deal with the hassle of (possibly incorrectly) explicitly marking functions as safe/unsafe (e.g. functional programming)

Note that I'm not saying which compiler here - it's very likely that you have 2 of them; one for converting the source code into some sort of intermediate representation, then a second compiler that converts the intermediate representation into native (e.g. the JIT compiler). In this case the first compiler can do all the slow stuff (like determining which functions are safe/unsafe), and the second compiler can avoid doing the slow stuff by relying on hints inserted by the first compiler.


Cheers,

Brendan

[AndrewAPrice]

I agree that a compiler is bad if it forces it upon the user. It's what I want to avoid doing.

Note that I'm not saying which compiler here - it's very likely that you have 2 of them; one for converting the source code into some sort of intermediate representation, then a second compiler that converts the intermediate representation into native (e.g. the JIT compiler). In this case the first compiler can do all the slow stuff (like determining which functions are safe/unsafe), and the second compiler can avoid doing the slow stuff by relying on hints inserted by the first compiler.

I think I can get this working for most use cases in my front-end compiler (the one that generates bytecode) - the only time that it will be more difficult is if a function is assigned to a non-const variable, for example:

Code: Select all

function do_something(callback) {
// does callback have side-effects?
}

Yet in most 'typical' cases (not callbacks or dynamically loaded libraries), I think we can tell if it has side-effects or not:

Code: Select all

var add = function(a, b) {
   return a + b;
};

add(1, 2); // we can tell there are no side effects

At compile time, I could check if the variable we're calling has only been assigned functions that definitely do not have side-effects. Then the front-end can compile separate a separate instruction - CallFunction (if we can 100% confirm there are no side effects) or CallProcedure (if in doubt).

While I'm against forcing the user to specific it for every case, I think there are situations when it would be useful to explicitly tell the compiler to think that a function has no side-effects.

Code: Select all

var add = function!(a, b) {
   // force the compiler to think add(a,b) has no side effects so it can be optimized
   io.writeToFile("log.txt", "We called add with " + a + " and " + b);
   // we could be assigning temporary memory here for the calculation
   return a + b;
};

add(1, 2); // the JIT front end can optimize this

This would offload most of the work to the front-end compiler - which is much better than slowing down JIT compilation - and the JIT compiler can use CallFunction/CallProcedure (the hint from the front-end compiler) to figure out if it should optimize it or not.

However, if I dynamically load a file at run-time:

Code: Select all

var super_duper_math_lib = require("./super_duper_math_lib");

super_duper_math_lib.cos(); // does this have side-effects?

var cos_wrapper = function(rad) {
    super_duper_math_lib.cos(rad);
    // we'd have to scan at load time to see if cos_wrapper has side effects or not
};

cos_wrapper();

..things get much more complicated.

[sortie]

You may be interested in attribute ((pure)) in compilers such as GCC. They assume that all functions have side effects for compatibility, but this attribute tells the compiler that it is not the case for that function and thus such side effects can be safely optimized away.

In a custom programming language it would depend on its design and use whether side effects should be assumed by default. You could require the person declaring the functions to always specify which case it is using special keyword like computational or effectful (or whatever you think those annotations should be called). If you do whole program optimization, you could likely construct proofs for all functions in a program whether they have side effects with few false negatives (that can easily be corrected with the addition of a keyword as an optimization).

[AndrewAPrice]

Thanks, sortie. Some functions are very easy to detect if they are 'pure' or not - for example:

Code: Select all

var power = function(a, b){
  var result = a;
  b--;
  while(b > 0) {
    result *= a;
    b--;
  }
  return result;
}

The compiler can see we are not touching any closures (actually the only way functions can touch anything outside of themselves in my language) so the compiler can automatically mark it 'pure'.

For more complex functions that the compiler can't determine, I don't mind the programmer explicitly saying:

Code: Select all

var cached_sqrt = pure function(val) {
  if(sqrt_cache.contains(val))
    return sqrt_cache.get(val);

  var result = math.sqrt(val);
  sqrt_cache.set(val, result);

  return result;
};

The problem with a dynamic language lies with the caller knowing if the callee is pure or not. Especially since the common libraries (such as math and io) are loaded at runtime, there's no way at compile time knowing if the function in the module you're going to load will be pure or not. If we wanted any reasonable way of knowing this at compile time, I'd have to load a table of known library functions into the compiler (which is messy and I want to avoid).

Alternatively, I could treat non-pure and pure functions as different types. My long term goal for my JIT compiler is to implement something similar to basic block versioning. If I were to treat these as two separate types, then there would essentially be two code paths when these types are encountered.

[Icee]

Unless your main objective is some practice with compiler construction, I'd suggest opting for an existing solution for performing code optimizations and even JIT. I'm talking about LLVM here.

The current state of the art in compiler construction is using LLVM as a middle-end, and sometimes as a back-end as well. If you are in need of a specific optimization (which is unlikely because most language-specific features would be lowered far enough to be irrelevant) you might as well implement it as an LLVM pass.

Writing compiler optimization routines from scratch is quite a tedious task, mostly because subtle implementation bugs can produce miscompiles that are hard to track down to the core issue.

However, should you decide on coding everything yourself, I'd suggest buying a copy of Muchnick's "Advanced Compiler Design and Implementation" and keeping it around as a reference. You will find the more advanced dataflow optimizations discussed in great detail there. Although the book is quite old, nothing much has changed in the optimization field since then.

Good luck (=

[AndrewAPrice]

Thanks Icee. I'm doing all of this from scratch (my own language, compiler, VM, OS) because it is fun and I'll learn a lot, even if it's not the best performing compiler or best language out there.

[Rusky]

The key with dynamic languages is to put all the type information and attributes with the values rather than the variables. The purity of a function goes on the function itself, and at that point you can do other kinds of analysis and optimization (constant propagation, etc.) to determine if a variable holds a pure function. This applies at the first run and also if you do optimistic JITs of particular executions of functions.

[AndrewAPrice]

The key with dynamic languages is to put all the type information and attributes with the values rather than the variables.

I do that in my interpreter. My variables are 9 bytes - 1 byte for type information (boolean, unsigned, signed, float, null, object, array, buffer, function pointer, string), and 8 bytes for a 64 bit value (value of the primitive type, or a pointer) - it keeps everything consistent, but it does waste memory.

If my JIT can tell that a type is a function pointer, a float, etc. then it's possible to 'unbox' the value (dropping the type) so it can fit into an x86-64 register, because the generated code will be hardcoded in to treat it as it's type - and at exit points where we re-'box' the value (wrapping it in a type) we can have that logic hardcoded in by the JIT pointer.

This is why I'm attracted to basic block versioning - having a hard coded path for each combination of types in basic blocks, although the theory of dropping the type isn't perfect as there are still points where we have to test variable types.

Alternatively, I could store the type in the high 4 bits of registers, which means all values will only be 60-bits? Will this be slow - having to do some bit shifting before/after every signed integer and floating point operation? What do you think?

[Brendan]

Hi,

Alternatively, I could store the type in the high 4 bits of registers, which means all values will only be 60-bits? Will this be slow - having to do some bit shifting before/after every signed integer and floating point operation? What do you think?

If a piece of source code has 123 different types of function pointers and 456 different types of structures; and if any of those things can have any amount of indirection (e.g. "a pointer to a pointer to a pointer to ... an array of myStructure"); then how many bits would you need to store all possible types?

If a programmer does "typedef int age;" and "typedef int distance;" does it make sense for a programmer to add an age to a distance and should the compiler warn about "incompatible types in addition"? Note: I honestly don't know if this question has an answer.


Cheers,

Brendan

[AndrewAPrice]

If a piece of source code has 123 different types of function pointers and 456 different types of structures; and if any of those things can have any amount of indirection (e.g. "a pointer to a pointer to a pointer to ... an array of myStructure"); then how many bits would you need to store all possible types?

Type in my language refers to language primitives - which may only be:

• Boolean
• Unsigned
• Signed
• Float
• Null
• Object
• Array
• Memory Buffer
• Function Pointer
• String
• Closure (internal garbage collected type, never exposed in code)

This is very different to a C-style system where every structure/class can be considered a different type. (If you were to compile C to my bytecode, you'd probably represent structs with memory buffers.)

[AndrewAPrice]

I've had some success with my compiler figuring out if you're calling a 'pure' function (a function is considered pure if code execution stays in the scope of the local closure and you are only reading constant non-aggregate closure variables.) Here is an example:

Shovel source code:

Code: Select all

var Test = require("Test");

var fibonacci_test = function() {
	var fib = function(n) {
		if (n <= 1)
			return n;

		return fib(n - 1) + fib(n - 2);
	};

	Test.begin("Recursive Fibonacci");
	var result = fib(35);
	Test.end(result);
};

fibonacci_test();

The compiled bytecode:

Code: Select all

Function f0
-closures 1
PushNull
PushString "Test"
Require
StoreClosure 0
PushFunction f1
Store 0
Grab 0
CallFunctionNoReturn 0
Function f1
-closures 1
PushNull
PushFunction f2
StoreClosure 0
PushString "Recursive Fibonacci"
PushString "begin"
LoadClosure 1
LoadElement
CallFunctionNoReturn 1
PushUnsignedInteger 35
LoadClosure 0
CallPureFunction 1
Store 0
Grab 0
PushString "end"
LoadClosure 1
LoadElement
CallFunctionNoReturn 1
Function f2
-parameters 1
Grab 0
PushUnsignedInteger 1
LessThanOrEquals
JumpIfFalse l1
Grab 0
Return
.l1
Grab 0
PushUnsignedInteger 1
Subtract
LoadClosure 0
CallPureFunction 1
Grab 1
PushUnsignedInteger 2
Subtract
LoadClosure 0
CallPureFunction 1
Add
Return

That's 214 bytes assembled into a binary file (with headers and metadata).

2 address/SSA instructions (the destination is the address of the instruction!):

Code: Select all

Compiling function.
Basic block (BB0) - 0 incoming parameter(s)
 0: Null
 1: String *3746464 ("Test")
 2: Require [1]
 3: StoreClosure 0, [2]
 4: Function *3750000
 5: CallFunctionNoReturn 0 [4]
Compiling function.
Basic block (BB0) - 0 incoming parameter(s)
 0: Null
 1: Function *3750144
 2: StoreClosure 0, [1]
 3: String *3750432 ("Recursive Fibonacci")
 4: String *3746880 ("begin")
 5: LoadClosure [1]
 6: LoadElement [4] [5]
 7: Push [3]
 8: CallFunctionNoReturn 1 [6]
 9: UnsignedInteger 35
 10: LoadClosure [0]
 11: Push [9]
 12: CallPureFunction 1 [10]
 13: String *3747456 ("end")
 14: LoadClosure [1]
 15: LoadElement [13] [14]
 16: Push [12]
 17: CallFunctionNoReturn 1 [15]
Compiling function.
Basic block (BB0) - 1 incoming parameter(s)
 0: Phi Basic Block Parameter 0
 1: UnsignedInteger 1
 2: LessThanOrEquals [0] [1]
 3: Push [0]
 4: JumpIfFalse BB2 [2]
Basic block (BB1) - 1 incoming parameter(s)
 0: Phi Basic Block Parameter 0
 1: Return [0]
 2: Push [0]
Basic block (BB2) - 1 incoming parameter(s)
 0: Phi Basic Block Parameter 0
 1: UnsignedInteger 1
 2: Subtract [0] [1]
 3: LoadClosure [0]
 4: Push [2]
 5: CallPureFunction 1 [3]
 6: UnsignedInteger 2
 7: Subtract [0] [6]
 8: LoadClosure [0]
 9: Push [7]
 10: CallPureFunction 1 [8]
 11: Add [5] [10]
 12: Return [11]

Kind of messy to follow, fib() calls turn into CallPureFunction, while Test.begin(), Test.end(), and fibonacci_test() calls turn into CallFunction/CallFunctionNoReturn. I'm doing no optimization yet, but when I start doing constant folding, common subexpression elimination, dead code elimination - the JIT compiler knows it's safe to eliminate/merge CallPureFunction instructions.

[AndrewAPrice]

I wrote a document describing how SSA and JIT will (eventually) be implemented in my VM: https://github.com/MessiahAndrw/Perception/blob/master/turkey/JIT.md

[Rusky]

I'm curious how your SSA instructions are so much bigger than your bytecode. A stack machine doesn't have to specify instruction inputs, but that shouldn't make things that much bigger. Specifying constants shouldn't matter much either, as that can use the same trick as a stack machine, using a separate op to store values. Are you just making them fixed-size to make reading them faster?

Basic block versioning looks really interesting- a cross between dynamic dispatch and generics with monomorphization, applied at a smaller level of detail. It would be interesting to see how it compares to tracing JITs and regular function-at-a-time JITs. The big tradeoff with memory explosion seems like it might be with the amount of dynamic dispatch- you could coalesce different versions by making them do more type checking. This might lead to a similar distribution of different code paths vs indirection compared to C++- code paths for generics and values, dynamic dispatch for objects.

It would be interesting to see how much basic block versioning and/or polymorphic inline caching could be applied at compile/startup time through static analysis. It could end up that at the bytecode level, your system is amenable to both dynamic, prototypal languages and more static ones.

[AndrewAPrice]

Are you just making them fixed-size to make reading them faster?

Yes, and for simplistic sake (I can read any instruction simply with an array index). Perhaps once I have something working it might be worth compressing it.

It would be interesting to see how much basic block versioning and/or polymorphic inline caching could be applied at compile/startup time through static analysis. It could end up that at the bytecode level, your system is amenable to both dynamic, prototypal languages and more static ones.

I've thought about this. Just how asm.js is a highly optimizable subset of Javascript (used by tools like Emscripten for compiling native code to JS), I think it would be possible to compile statically typed languages in such a way it hints to the VM (using a specific pattern or bytecode subset) that types are known at start-up time.