Hi everyone,

I'm having a serious bash at developing pure functions for FPC now, specifically 'node emulation' so it can step through a pure function and compute output values.  One of the small problems I'm trying to solve is keeping track of the state of variables, some of which are record types or otherwise non-standard (e.g. _m128). Just before I develop something that isn't cross-platform, is it acceptable to use GetMem (and the use of pointers) and TVarRec on all platforms? (note I'm using TVarRec, not the Variant type).

Gareth aka. Kit

As I assume you mean inside the compiler, then yes, those are features that can be considered available on systems the compiler works on. Though you'll have to check whether TVarRec is the right choice for you (no, definitely not Variant!), because due to Delphi compatibility it does not contain a LongWord field. Maybe instead you'll want to use something like TConstValue or some new record that contains the necessary information? How do you plan to use it, that might give enough hints to decide what to do?

Regards,
Sven

Hi Sven,

Thanks for the response.  Yes, this is all inside the compiler. Basically I need a means to keep track of the internal state of a function as I step through the nodes (a process I call 'node emulation'), namely local variables, parameters (if they're not const, they're basically just like local variables), and the function Result and out parameters.  Since these may be all sorts of things like integers, floating-point values, strings or record types, I need a system that can handle all of these value types. I figure the compiler has an existing structure somewhere, but I'm not sure what it is.

The other use of such a structure for handling these values is to store the results of the emulation, so as to save time.  If you had the following pure function (I'm aware it's not the most efficient implementation of the factorial operation):

function Factorial(n: Cardinal): Cardinal; pure;
begin
   if (n <= 1) then
     Exit(1)
   else
     Result := n * Factorial(n - 1);
end;

(I'm using "Exit(1)" so I have a different set of nodes to test)

Say you calculate Factorial(4) - you get a result of 24.  Later on, you may want to calculate Factorial(5), but when it reaches the recursive call, it can look up Factorial(4) to see it has already calculated that to be 24, and so simply recall that value instead of going through the whole process again and hence obtain the answer of 120 far faster.  It's the main argument I have against making all functions pure until proven otherwise... it would take the compiler a long time to determine if the function actually is pure etc (especially if you do something malicious like program an infinite loop).

The above function is quite simple, since I only need to track "n" and "Result", both Cardinals, but there may be cases where I need to track strings (e.g. "IntToStr" / "tostr" could be pure functions, which would allow for further optimisations as it means other pure functions are permitted to call them).

Gareth aka. Kit

It's called constant propagation. -Ooconstprop enables this, but the current support is very limited.

Jonas

Constant propagation is only really beneficial for inline functions, although there is some crossover with pure functions. I was more meaning a system of tracking and storing these constants, or rather how they manipulate variables throughout a pure function.

I've also found some annoying limitations with constant propagation that leads to a lot of dead code.  The biggest example of this is in the compiler itself with the peephole optimizer's debug messages that are meant to be dummied out in a release build.  The string concatenation functions are still called, because the compiler can't see that the individual string fragments, which come from other functions, are constant ("StrConst1 + StrConst2" is otherwise concatenated at compile-time).  Pure functions will help here, although admittedly with this example, I might consider re-evaluating how strings are concatenated in the node passes, since if there are more than 3 parts to concatenate, it's built in a way that doesn't give the compiler a chance to merge adjacent string constants, among other things.

The main thing with pure functions is that constant propagation is far more in-depth, and that its result can be assigned to a constant (e.g. const RootPi: Double = Gamma(0.5);", if Gamma is defined as "function Gamma(const N: Double): Double; pure;"... the value of the function is computed at compile-time and only its result is stored in the binary).  There are also some optimisations you can potentially make in the knowledge that a pure function doesn't have any side-effects.  For example, if N, X and Count are Integers:

for N := 0 to Count - 1 do
begin
   SomeOtherProc(N * SomePureFunc(X));
end;

Here, because X is not modified by the for-loop, the entire call to SomePureFunc can be moved outside of the for-loop and its result stored for re-use - that is, the equivalent of:

R := SomePureFunc(X);
for N := 0 to Count - 1 do
begin
   SomeOtherProc(N * R);
end;

Even though the value of X is unknown, because pure functions have no side-effects, it is guaranteed to give the same output for a given input.

The C++ equivalent of this functionality is the 'constexpr' directive.

To get back to my original question, I'm going to be using TConstValue for now for most things, and using its ability to store pointers and lengths for more complex things like records, arrays and strings.  Thanks for the suggestion Sven.

Gareth aka. Kit

J. Gareth Moreton wrote

Constant propagation is only really beneficial for inline functions,

That is incorrect.

although there is some crossover with pure functions. I was more meaning a system of tracking and storing these constants, or rather how they manipulate variables throughout a pure function.

That is exactly what -Ooconstprop does, although (as mentioned before), to a quite limited extent. It doesn't extract the constants from the nodes, but replaces variables (load nodes) with the constant nodes that were assigned to them earlier, and then at the end runs the simplify pass over the resulting node tree. The simplify pass already contains all support for merging expressions involving only constant nodes into single constants, so it has no need for storing the constant data in a separate structure and then duplicate all the constant evaluations for that extra structure.

Jonas

So are you officially rejecting pure functions and my future work on them in this form?

Gareth aka. Kit

J. Gareth Moreton wrote

So are you officially rejecting pure functions and my future work on them in this form?

I'm just trying to say that there is already a (primitive) framework for propagating constant values through functions (in the optconstprop unit), and also an extensive framework for evaluating constant expressions (the simplify methods of all nodes), and that hence there may not be any need to develop a completely new constant evaluation and propagation framework next to this.

I explained before that I am absolutely no fan of a "pure" attribute, but that has nothing to do with my remarks here. And no, I will not veto the inclusion of manual annotations of pure functions.

Jonas

Assuming we want to have support for constant evaluation of functions (and I do admit that sometimes that is a really nice to have), I don't really see a way around marking such functions somehow, cause otherwise we'd have to store the node trees of all functions that we detect as pure in the PPU.

Regards,
Sven

That and also attempting to propagate or evaluate every single function you come across will make the compiler prohibitively slow.  Inline functions benefit most from constant propagation because a copy of the node tree exists and you can often cut away entire branches based on the propagation of constant input parameters.

Pure functions are a slightly tricky one because there is a lot of overlap with inline functions and constant propagation, and yet there are concepts that aren't covered by either, such as 'promotion' of pure function calls outside of loops and assignment of pure function results to compile-time constants.  Also, pure functions can be recursive, like with the factorial function, but there will have to be safeguards against infinite loops or other constructs designed to break the compiler in that regard (e.g. the Ackermann Function).

I'm sure others can come up with uses for pure functions.

Gareth aka. Kit

Detection of pure functions (or what LLVM calls read-only) functions is useful in its own right, e.g. for loop hoisting (like in Gareth's example). You preferably don't limit that to functions that have been manually annotated as "pure".

And if you have to do that anyway, then also storing the node tree is not that much extra work. Whether or not you actually evaluate/inline that entire node tree, depends on the inline settings (most compilers have tuning parameters that allow you to set complexity limits for that).

Being able to call arbitrary functions (marked as "pure") in declarations of constants is indeed also the only real use-case I see for manually marking them as "pure". After all, you don't want to be in the situation where you call a function from a third party unit as part of a constant declaration, and then get a compile error with the next version of that unit because that same function happens to be no longer pure (or the compiler can't prove it anymore). It's part of an interface contract in that way.

However, that is also it's biggest downside: I think this can easily lead to issues if the clean way to implement a change would be by making a previously "pure" function non-pure. You then can't do that because it would break users of your code that rely on this function being pure, so you have to program around that (i.e., you painted yourself into a corner). It's similar to how you can easily get into issues with non-trivial "const" methods in C++, where one removal of "const" can cascade into hundreds of errors all over the place.

And while I have encountered cases where I would have liked to be able to call a particular function in a constant declaration, it doesn't happen often enough that I perceive it as something that is really missing.

Jonas

Your original message stated that you were looking at a way to develop "'node emulation' so it can step through a pure function and compute output values".

I'm not saying "the constant propagation optimisation does the same as pure functions". I'm saying "'node emulation' of a function is the same as constant propagation through that function, pure or not".

Jonas

I'm glad we agree that one benefit of pure functions is loop-hoisting.  I call them pure functions because that's the technical name for them: https://en.wikipedia.org/wiki/Pure_function - they're analogous to a mathematical function.  'Read-only' sounds a little ambiguous to me and not immediately certain as to what is actually read-only. Granted, the meaning of 'pure' doesn't immediately jump out either, but the lack of side-effects and consistent outputs for a given inputs are the necessary criteria to be defined as such.

The "pure" directive, or the lack of it in most functions, helps takes pressure off the compiler, while its presence aids the programmer by explicitly stating that 'this function is pure' and can be used as such.  If a third-party library removes the purity of a function compared to an earlier version, I would put the blame on the programmer of the library rather than the language itself.  There will always be cases where you've screwed yourself over and have to change things, like the addition of a new parameter in a subroutine.

I suppose node emulation would be equivalent to constant propagation.  I sense we might need to refactor things afterwards so the same code can be reused for both purposes.  My current design for the emulation would introduce a new virtual method for TNode that descendants override to perform their specific behaviour, rather than have it all in a monolithic 'propagate' procedure.  By default, this method would return a 'fail' code to indicate the function is not pure (a function that is marked as 'pure' but is discovered not to be will raise a compiler warning, and an error if it's part of a constant assignment), so you don't have to program something for every single node and the introduction of a new node type won't break the emulator.

I think the difference between constant propagation and node emulation in this regard is that the former is trying to simplify nodes and eliminate conditional branches that will not be executed, among other things, while the latter is trying to generate a single output (or multiple if the routine has "out" parameters).

Gareth aka. Kit

Well, Jonas is right that if you have a node tree that only has constant nodes as inputs the tnode.simplify method should (in theory) be able to completely collapse that (under the assumption that this is also handled by call nodes and such).

Maybe as a first step you could try to
- determine the likely constness of a node during typechecking (the final result can then be stored in the implprocoptions of tprocdef)
- store the node tree if it can possibly be pure
- improve simplify of nodes to make use of that
- have this be used in node tree optimizations (like the loop-hoisting you mentioned)

If this works correctly we'll already have a first optimization that makes use of this and we can in principle see whether the concept works without introducing some emulator. After that we can still decide to allow this for constant declarations (with or without a pure attribute).

Regards,
Sven

Sven Barth wrote

Well, Jonas is right that if you have a node tree that only has constant nodes as inputs the tnode.simplify method should (in theory) be able to completely collapse that (under the assumption that this is also handled by call nodes and such).

Simplify by itself cannot do that, but simplify + constant propagation can (once constant propagation gets extended). There is no reason why it should not be able to handle out-parameters, and it can already collapse entire (simple) functions into a single assignment of a constant to a function result (when combined with -Oodeadstore).

I cannot think of a single reason why a particular propagation/simplification/emulation/... feature should not be supported by constant propagation, but should be supported when evaluating pure functions.

Jonas

It's likely that this feature may go through several iterations before we settle on some code that everyone is happy with.  At the moment I'm trying to design and develop a system that captures everything, like propagating through nested or recursive calls and calling internal functions that are, by all accounts, pure (e.g. Sqrt).

Constant propagation and simplification isn't perfect, especially where there's implicit typecasting and inline expansion.  Room for improvement elsewhere.

Gareth aka. Kit

Currently I'm not using the constant propagation code for the pure function feature, but after some refactoring down the line, hopefully they can be made to use the same code and hence improve both features drastically.  Note that my 'node emulation' feature for pure functions doesn't transmorph the nodes, although I imagine it wouldn't be too difficult to include this ability.

Gareth aka. Kit

J. Gareth Moreton schrieb am Do., 30. Apr.
2020, 17:07:

You might want to look at constant propagation first, cause that might increase the chances of your changes being included. And it would benefit existing code already.

Regards,
Sven

I guess so.  I'll see what I can do and if the constant propagation system is good enough to be expanded.  At the moment I'm trying to get something to work, then build from there.

Gareth aka. Kit

One problem I have been running into due to the use of TConstValue are circular unit references - I've had to move some definitions to different units to get around it.

Gareth aka. Kit

Is there a good way to show you guys the work in progress and for you to make more informed comments on the design along with any bugs and shortcomings?  I'm making progress with make a pure factorial function, but it's nowhere near ready for general use.

Gareth aka. Kit

On May 1, 2020, at 6:46 AM, J. Gareth Moreton wrote: Is there a good way to show you guys the work in progress and for you to make more informed comments on the design along with any bugs and shortcomings? I'm making progress with make a pure factorial function, but it's nowhere near ready for general use.

Do you have GitHub? if so put your work into a feature branch and we can browse your changes by , Ryan Joseph

Okay, I'll give that a try - do I need to post the entire FPC repository there with my changes, or just the diff/patch files?

Gareth aka. Kit

On May 1, 2020, at 4:05 PM, J. Gareth Moreton wrote: Okay, I'll give that a try - do I need to post the entire FPC repository there with my changes, or just the diff/patch files?

It shows the diffs for you. Fork the FPC project on GitHub (https://github.com/genericptr/freepascal) then clone it locally and make a new branch. Then you can navigate to the feature branch, for example on my GitHub I have a branch for "static array initialization":

https://github.com/genericptr/freepascal/tree/static_array_init

If you can find the little compare button you'll get a URL like this:

https://github.com/graemeg/freepascal/compare/master...genericptr:static_array_init

That shows the commits and changed files as a diff. It happens all automatically so all you have to do is push changes (in your git client or what ever you use).

Regards,
Ryan Joseph

I'm still learning these things - bear with me!  I'll get one set up when I have something preliminary working.

At the moment I haven't been able to unite the constant propagation code with my pure functions because they work in fundamentally different ways
- for inline functions constant propagation makes a copy of a node tree then transmorphs them as it propagates the constants, while my code just takes the node tree and steps through it without modifying it.  I guess there's merits for both approaches, but because of pure functions' ability to be recursive, I'm worried about malicious functions causing a massive ballooning of nodes and memory issues before the compiler detects an infinite loop (or one that is simply too long) before destroying all of the nodes again, throwing a warning and keeping the original call node.  Also, there are places where nodes can't actually be used, like in the definition of constants, and they simply have to have their results calculated.

We'll see though - this could prove to be insightful.

Gareth aka. Kit

I see no sense in doing so. It adds another method to do constant folding which needs to be maintained.

There needs to be a procedure/approach to check if a function can be pure. That's it. Rest can be done using the currently available constant folding/propagation code.

Well, as I've found, there is no straightforward method to actually determine if a function is pure or not.  For example, if it stumbles upon a procedural call, which may be itself (recursion), it doesn't immediately know if that call is to a procedure that is itself pure or not.  There are also problems if calculating the value of a pure function may raise an exception (either by explicitly calling 'raise' or doing an integer division by zero, for example), something that breaks things down when assigning pure function results to constant definitions.  And let's not get started if the pure function contains a deliberate infinite loop!

Gareth aka. Kit

Generally, the way to deal with recursion is to start by assuming it is in fact pure (or whatever property you are checking). If it is still considered pure once you processed it entirely, then the property holds.

There are also problems if calculating the value of a pure function may raise an exception (either by explicitly calling 'raise' or doing an integer division by zero, for example),

A function that explicitly raises an exception can never be pure, since an exception changes global state and there is no way to know what raising this particular exception means (e.g., it could a hack to return a value several levels up the stack, or to implement an interprocedural goto). It might indeed not raise an exception for particular inputs, but that is no different from a function that e.g. does not read from or write to any global data for certain inputs.

Implicit exceptions, i.e. run time errors, are different. In that case you will get a compile-time warning or error similar as during normal constant evaluation, depending on the active switches like range checking.

something that breaks things down when assigning pure function results to constant definitions.  And let's not get started if the pure function contains a deliberate infinite loop!

This requires limiting the number of evaluation steps/iterations.

Jonas

Maybe I've fallen into a trap of sunken cost fallacy or being too proud of my own code rather than properly looking at what's already available.  Part of my fear with using the constant propagation code is that it constantly copies and transforms the nodes every time the pure function needs to be evaluated, which I'm concerned will incur a notable speed penalty.

I reuse the node tree that inline functions get, thereby saving storage in the PPU file.

Regarding determining if functions are pure or not, I have two flags to
help determine this;

- the first is "po_pure" under tprocoptions, which is set when it sees the 'pure' directive, and is cleared (with a compiler warning) if the compiler spots something that makes the function ineligible (e.g. raising an exception, an uninitialized variable, accessing a static variable etc.)
- the second one is "pi_pure_uncertain" under tprocinfoflags. This is set when the node builder sees something that makes it uncertain if the function can be pure or not, although it might still be possible (e.g. calling another procedure, and currently the presence of 'raise', 'goto' and any kind of loop, due to the risk of it being infinite)

The "pi_pure_uncertain" flag may be unnecessary, but if it remains clear by the time 'pass_1' is finished and the procedure doesn't have the 'pure' directive, the compiler is able to drop a hint to say that the function is eligible, since the function has completely linear flow and isn't accessing anything outside of its scope.

For the limit on how many nodes to evaluate before it drops out, I had a counter in the node emulator class that was a static variable, incrementing every time a node is evaluated (it's a static var because a new emulator object was instantiated if if the first one came across a call to another pure function).  How should I implement a node counter with the constant propagation code?

For one final speed-up, each function that is pure can store previously-calculated results for a given set of parameters; e.g. after calculating Factorial(5) = 120, the compiler can recall this answer (or a copy of the nodes that give the answer) for subsequent calls to Factorial(5), thereby reducing compilation time and memory strain.  It does subtly increase the node limit before it drops out on loops or recursion that are excessively long, but not infinite (e.g. the Ackermann Function), but this shouldn't incur a performance penalty.

I'll shelve my node emulator for now because of it being entirely separate to the constant propagation code, and see if I can adapt the constant propagation code.

Gareth aka. Kit

So I got my salvaged code transferred over, now I'm mostly researching the constant propagation and inlining code.  I may have to make adjustments to the constant propagation code so i can reuse it, so I can introduce things like a node counter (to catch infinite loops) as well as allow the use of TCallNode (I'll probably just modify the structure that the 'arg' parameter points to so it can contain flags and a counter and the like).

The one I'm still working out theoretically is determining if processing the pure function this way has actually yielded a straightforward result and not some complex node tree.  Ideally, it should be just a simple tree that writes the answer to the temporary result storage (and any 'out' parameters that exist, although given this approach, it might work with 'var' parameters as well in some situations).  If it's a more complex tree that manipulates variables, then it should reject it and just call the function conventionally (and throw a compiler warning to indicate the function is not pure).

There is one other situation where a function might be pure but not inline... if the function is so large that making it inline is extremely wasteful, but is otherwise technically a pure function and will give a deterministic result for a given input.  An example might be a function that calcuates a MacLaurin series in order to produce a result of the desired precision.

Gareth aka. Kit