Hi everyone,

So I thought I'd do a little progress update on the pure function research.

So far I'm mostly researching how the node builder works, specifically how inline functions are handled, since that's a situation where a 'call' node is effectively replaced, and I intend to builda similar system to handle pure functions.

Designing an emulator to step through the nodes is a little tricker if only in regards to where it should slot into the project. It's a fun challenge, but probably one of the most technical problems I've undertaken to date.

The full design is a little awkward because I want to cover every eventuality, which is hard to predict. Fully self-contained functions with only a single output parameter (i.e. the result) are relatively straightforward as I don't have to handle any calls to other pure functions, and the 'call' node can be replaced with a node representing a literal of some kind once it's calculated, but it gets more complicated if other pure functions are called inside it, there are 'out' parameters or there are difficult situations like infinite loops or code paths that simply take too long to complete. There's also testing required to see if the functions still work with partial compilation (i.e. where some PPU files aren't rebuilt).

As stated in the Wiki page, my first test case is the Max function. Since it works both as an inline and a pure function, I can easily change the directive to analyse the code flow in the compiler.

Gareth aka. Kit

J. Gareth Moreton wrote

As stated in the Wiki page, my first test case is the Max function. Since it works both as an inline and a pure function, I can easily change the directive to analyse the code flow in the compiler.

I may have missed this in the discussion before. But isn't that a prime example for "simple" const propagation?

==========================================
function Max(a, b: integer): integer; inline;
begin
  if a > b then
    Result:= a
  else
    Result:= b;
end;
  z:= Max(1, 2);
==========================================
That already gets optimized to `z:= 2;` on -O1, while the following needs -O2,
but gets to the same result:
==========================================
  x:= 1;
  y:= 2;
  z:= Max(x, y);
==========================================

Tail recursion expansion could do the same for certain recursive functions.

In that situation, yes it is. Max is a very simple function though, and it gets more complicated if it appears in another pure function where the parameters are variables, but whose values are deterministic. In the end, Max is a function that can be pure and inline.

For optimization, I figured to keep error checking and debugging consistent, the compiler will attempt to evaluate the value of such functions at compile time (so any errors are brought to light), but only replace the function call on -O2 and higher.

Gareth aka. Kit

On Mon 16/07/18 11:43 , Martok sent:

The discussion about the potential implementation left me a bit confused. I think part of what might need to happen is a better type system, in part to keep track of constant expressions.

Cheers,
R0b0t1

J. Gareth Moreton wrote

In that situation, yes it is. Max is a very simple function though, and it gets more complicated if it appears in another pure function where the parameters are variables, but whose values are deterministic.

Actually, this might be more workable than I "Thing from -O3" that carries out the simplification in my example (it also works for mixed things like "x:= 1; z:= Max(x, 2);") is exactly the constant propagation optimization. It might be enough to simply force a few localized optimizations after inlining and before simplifying.
I'll have a look into that later - this would be useful for many cases regardless of pure functions.

I’ve looked at the FPC sources recently but I still don’t understand the basics. I see lots of TDef,TSym,TSymTable classes. What are those used for? You mentioned nodes and I wonder if that’s what those are.

Regards,
Ryan Joseph

Ryan Joseph schrieb am Mi., 18. Juli 2018,
01:27:

Symbols are the named variables, types, functions, etc. of a module. Definitions are their type. Two different symbols can point to the same type, e.g. when using a type alias or simply when declaring two variables of the same type.
Symbol tables are exactly what it says on the tin: a table of symbols. They're either the fields of a class/record, local variables of a routine, the parameters of a routine or symbols declared in the interface or implementation part of a unit.
Nodes are essentially FPC's abstract syntax tree. They represent operations (e.g. load symbol X, add symbols Y and Z, access symbol V using symbol I as index, etc.). These nodes are then converted by the code generator to machine code. Or are also stored as is in the PPU for inline functions, so that the compiler does not need to reparse the source (which might not be available after all).

Regards,
Sven