Discussion:
Progress of pure function research
(too old to reply)
J. Gareth Moreton
2018-07-16 05:01:46 UTC
Permalink
Raw Message
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
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/
Martok
2018-07-16 10:43:58 UTC
Permalink
Raw Message
Am 16.07.2018 um 07:01 schrieb J. Gareth Moreton:
> 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.


--
Regards,
Martok


_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://list
J. Gareth Moreton
2018-07-16 16:54:51 UTC
Permalink
Raw Message
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 ***@martoks-place.de sent:
> Am 16.07.2018 um 07:01 schrieb J. Gareth Moreton:
>
> > 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.
>
>
>
>
>
> --
>
> Regards,
>
> Martok
>
>
>
>
>
> _______________________________________________
>
> fpc-devel maillist - fpc-***@lists.freepascal.org
> http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
>
>
>
>

_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/l
Martok
2018-07-17 17:44:28 UTC
Permalink
Raw Message
Am 16.07.2018 um 18:54 schrieb J. Gareth Moreton:
> 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 thought at first. The "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.

--
Regards,
Martok


_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.f
R0b0t1
2018-07-16 18:00:37 UTC
Permalink
Raw Message
On Mon, Jul 16, 2018 at 12:01 AM, J. Gareth Moreton
<***@moreton-family.com> wrote:
> 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.
>

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
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-
Ryan Joseph
2018-07-17 22:55:34 UTC
Permalink
Raw Message
> On Jul 15, 2018, at 11:01 PM, J. Gareth Moreton <***@moreton-family.com> wrote:
>
> 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.

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

_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://l
Sven Barth via fpc-devel
2018-07-18 05:39:18 UTC
Permalink
Raw Message
Ryan Joseph <***@thealchemistguild.com> schrieb am Mi., 18. Juli 2018,
01:27:

>
>
> > On Jul 15, 2018, at 11:01 PM, J. Gareth Moreton <
> ***@moreton-family.com> wrote:
> >
> > 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.
>
> 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.
>

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

>
Loading...