Hi everyone,

I've made a bit of a breakthrough with the development of pure functions.  I've successfully managed to get the compiler to calculate the factorial as a pure function in two different forms... one usig a for-loop, and one using a recursive call (which is where it differs from 'inline').

It's nowhere near ready and I haven't tested floating point numbers or strings yet (and error messages and warnings etc. are still lacking).  Only const and value parameters are accepted currently.  I haven't included support for "out" parameters because functions that return a value and have an "out" parameter aren't inlined and would be a little bit tricky to build a valid node tree for.

Find it here: https://gitlab.com/CuriousKit/optimisations/-/commits/pure

I welcome anyone to test it out and try to break it!  To confirm if the compiler has interpreted a subroutine as a pure function, the best way is to look at the node tree with DEBUG_NODE_XML, specifically the result of the "firstpass" section.

I've also attached two code examples that contain the factorial functions.

Kit

The next big milestone that I want to achieve is to make this a pure function:

procedure int_str_unsigned(l:longword;out s:shortstring); pure;
var
   m1 : longword;
   pcstart,
   pc2start,
   pc,pc2 : pchar;
   hs : string[32];
   overflow : longint;
begin
   ;
   pc2:=pc2start;
   pcstart:=pchar(@hs[0]);
   pc:=pcstart;
   repeat
     inc(pc);
     m1:=l div 10;
     pc^:=char(l-(m1*10)+byte('0'));
     l:=m1;
   until l=0;
   overflow:=(pc-pcstart)-high(s);
   if overflow>0 then
     inc(pcstart,overflow);
   while (pc>pcstart) do
     begin
       pc2^:=pc^;
       inc(pc2);
       dec(pc);
     end;
   s[0]:=char(pc2-pc2start);
end;

This is essentially the core internal function that drives IntToStr and similar functions.  The challenges here include:

- A repeat...until loop with no obvious termination sequence.
- Using a pointer to access an array offset of a local variable.
- Writing characters (and the length field) one at a time to a shortstring.

The reason for wishing to make IntToStr a pure function is that for a given input, the output will never change, and it's perfectly feasible for some other function to call IntToStr as part of a string generation routine and which would otherwise itself be a pure function (if a pure function wishes to call another function, it must also be determined to be pure... see pure1b.pp for the recursive example where the actual parameter isn't even a constant, but is nonetheless deterministic).

Kit

So there are bugs in my pure function code, specifically with the use of current_procinfo - I didn't realise until now that the one relating to the current function is actually freed after the body has been parsed.

Ideally I would have gone the approach of reusing more of the pass1_inline code and replacing the local variables and parameters with temprefs, but data flow analysis doesn't yet work properly with temprefs (and I haven't been able to work out why... basically if I let them get included, their life information isn't filled in, so dead-store elimination will strip ALL of the definitions, even the ones that are very much needed).  I'll keep at it!

Kit

Fixed that bug!  Also fixed a bug where the code analysis would get upset if you have "X mod Y" behind a "if (Y 0) then" check, and Y evaluates to zero.  I've attached a new test project to showcase this (and which revealed the aforementioned bug).  My branch also correctly replaces the function call with the number 12.

Kit

J. Gareth Moreton via fpc-devel schrieb am
Di., 13. Dez. 2022, 22:09:

Wouldn't it make more sense to ensure that the Str() and Val() intrinsic work correctly inside "pure" functions? After all the compiler can then simply evaluate the inlinen nodes and does not have to "interpret" a ton of other code as well.

Regards,
Sven

Heh, I had a feeling I was overcomplicating it - thanks Sven. I'll start experimenting on that one.

On a similar note, my branch has a number of other merge requests embedded in it, namely the "typeconv-strip" and "nothing-strip" branches (!232 and !342 respectively) and these are requred to simplify the node trees during purity analysis.  Some node classes that represent intrinsics may require additional programming in order to convert them into their actual results.

I'm also trying to think what cases I'll need to cover, both positive and negative - for example:

- Calling a pure function with a variable actual parameter (the formal parameter is constant or passed by value) will call the function conventionally, but not flag it as impure.
- If a function is marked as pure, any references to non-local symbols (other than constants that can be immediately resolved) will throw a compiler warning and mark the function as impure.
- Any code path that results in a non-deterministic result (might only be possible when trying to analyse it for a given input) will throw a compiler warning and mark the function as impure.
- If purity analysis throws a compiler error (e.g. a division by zero), this will cause the program to fail to compile.

Some cases might be immediate compiler errors though - for example, explicitly raising an exception in a pure function is essentially forbidden.

To better explain how purity analysis currently works (I'm sure there's a better name than "purity analysis"), it takes a copy of the unoptimised node tree (this is the same as the tree used for inline, and for a space saving, they share the same field), adds explicit definitions for the formal parameters so they equal the constants passed in, and then tries to collapse the node tree down to a single assignment to the result.  This is done by running the following operations in this order:

- Constant propagation
- For-loop unrolling
- Inline simplify (this will remove a lot of conditional branches from the tree; without it, the first pass below will raise an error if it comes across "if (Y 0) then Result := X mod Y;", for example)
- First pass (needed to parse nested pure functions)
- Dead store elimination

The process is repeated until no more changes are made.

There are some bailout conditions, some of which I don't know should be considered 'critical' (i.e. mark the function as 'impure') or not:

- If the recursion exceeds a certain depth (currently set to 64).
- If the node count exceeds a certain limit (currently set to 1,024).
- If a for-loop could not be successfully unrolled (this generally only happens if the start and end values are not constant).
- The first pass stage raises a compiler error (this is a genuine error case and the compiler will not build the program).
- The node tree does not simplify into a simple assignment to the result.

For the recursion and node count limits, I plan to test it on the Ackermann function:

function Ackermann(m, n: Cardinal): Cardinal; pure;
begin
   if m = 0 then
     Result := n + 1
   else if n = 0 then
     Result := Ackermann(m - 1, 1)
   else
     Result := Ackermann(m - 1, Ackermann(m, n - 1));
end;

This is also a good example to test for overflow conditions (which should be classed as an error), since the correct answer to Ackermann(4, 2), for example, has 19,729 decimal digits!

Note: marking the function as impure, when the compiler knows that a function is not actually pure in some circumstances, will speed up further compilation.

In the end, I will also try to implement a system where, after an output is calculated for a given input, the compiler will try to remember it so if the same inputs appear again in the program, the compiler does not have to recalculate the output and can just retrieve it.

Kit

So I just tried a simple test with "System.Str(5, Output);" (with Output defined as a string), and it produced the following nodes:

<calln resultdef="$void" pos="12,3">
...<procname>$fpc_shortstr_sint(Int64;Int64;out OpenString;&lt;const Int64&gt;);</procname>
...<callparan resultdef="Int64" pos="12,3">
......<ordconstn resultdef="Int64" pos="12,3" flags="nf_explicit" rangecheck="TRUE">
.........<value>255</value>
......</ordconstn>
...</callparan>
...<callparan resultdef="OpenString" pos="12,23">
......<loadn resultdef="ShortString" pos="12,23" flags="nf_write"> .........<symbol>OUTPUT</symbol>
......</loadn>
...</callparan>
...<callparan resultdef="Int64" pos="12,3">
......<ordconstn resultdef="Int64" pos="12,3" rangecheck="FALSE"> .........<value>-1</value>
......</ordconstn>
...</callparan>
...<callparan resultdef="Int64" pos="12,15">
......<ordconstn resultdef="Int64" pos="12,15" rangecheck="FALSE"> .........<value>5</value>
......</ordconstn>
...</callparan>
</calln>

This is before the first pass, so the parser immediately replaces it with a call to the internal compiler procedure.

How should I handle this? There are a few problems I need to consider.  If I use a new kind of inline node that expands into a regular call after the first pass, I'll still need to handle the case where it is a call node because there are situations during purity analysis where nested pure functions are not analysed because their actual parameters haven't yet been fully calculated (usually requires another found of constant propagation and inline simplification).  It may be that I need to add some kind of field to the TCallNode to indicate which internal function it's referring to.

I'll try to do a new merge request soon so Str and Val can be simplified at the node level, as this can easily have benefits outside of pure functions.

Kit

So it turns out that an "inlinen" node is created initially, but it is transmuted into a "calln" node by the typecheck pass almost as soon as it is created.  I think the reason it is transmuted so soon is because differently-named internal procedures have to be called depending on the input types.  I think the easiest way I can handle this is to add a new optional field to indicate which class of internal functions the node was generated from, and pass_1 can perform unique processing on it if certain criteria are met... and if they are not met, or the field is set to a value the compiler doesn't recognise, it just falls back to regular call-node handling.

Kit

So progress report on converting "Str(constant, output)"... it's not easy!  Firstly, after the first pass, a call node's parameters can get reordered so they can be placed into ideal registers or on the stack.  I found a workaround for that by adding a new field that records their original right-to-left ordering.  Despite the headache, I managed to consistently change it to an assignment of a string literal to the output variable.  Success, right?  Wrong! The first pass converts such an assignment to another call node!

<calln resultdef="$void" pos="12,3" flags="nf_pass1_done" complexity="255">    <procname>$fpc_shortstr_to_shortstr(out OpenString;&lt;const Int64&gt;;const ShortString);</procname>
   <callparan resultdef="ShortString" pos="12,3">       <stringconstn resultdef="ShortString" pos="12,3" flags="nf_pass1_done" complexity="1">
         <stringtype>shortstring</stringtype>          <length>1</length>
         <value>5</value>
      </stringconstn>
   </callparan>
   <callparan resultdef="OpenString" pos="12,3">       <loadn resultdef="ShortString" pos="12,3" flags="nf_pass1_done,nf_write" complexity="1">
         <symbol>OUTPUT</symbol>
      </loadn>
   </callparan>
   <callparan resultdef="Int64" pos="12,3">
      <ordconstn resultdef="Int64" pos="12,3" flags="nf_pass1_done,nf_explicit" complexity="0" rangecheck="TRUE">          <value>255</value>
      </ordconstn>
   </callparan>
</calln>

(The third "255" parameter seems to be some kind of encoding parameter)

Here, the original line of code was "Str(5, Output);".  This is actually pretty difficult to solve.

It might be that I have to find a way to perform purity analysis without ever calling firstpass on the node tree, which is currently needed for processing nested pure and inline functions... granted, I can possibly do that selectively using "foreachnode" or "foreachnodestatic".

Kit

What do you mean with “share the same field”? A pure function might still be called and inlined like a normal function and for that you shouldn't transform the node tree needlessly as that might influence the debugging experience. So you should have two different copies, one for inlining and one for pure related transformations.

Regards,
Sven

What I mean is that if a function is marked as "pure" or "inline" (or both), only one copy of the unoptimised node tree is stored in the "inlininginfo" field, and both "pass1_pure" and "pass1_inline" duplicate this tree and transform it as needed.  Because only the unoptimised tree is stored, I felt there was no need to store this twice (doing so would also increase the size of PPU files).

Kit

The purity analysis process is very dependent on the node tree being as clean as possible, and so depends on a fair few merge requests that have not yet been approved.  I'm guessing Florian and Jonas and others are somewhat busy, what with being December and all.

- https://gitlab.com/freepascal.org/fpc/source/-/merge_requests/232 - strips unnecessary typeconv nodes (this helps a lot with constant propagation).
- https://gitlab.com/freepascal.org/fpc/source/-/merge_requests/342 - strips excess nothing nodes.

Kit

I didn't say that you shouldn't clean up the tree for your purity analysis (that sounds so wrong :P ), I simply asked what you meant with “share the same field” and if it is what I think it is then it's a bad idea and you shouldn't “share the same field” but introduce your own.

Regards,
Sven

The field sharing refers to this:

"What I mean is that if a function is marked as "pure" or "inline" (or both), only one copy of the unoptimised node tree is stored in the "inlininginfo" field, and both "pass1_pure" and "pass1_inline" duplicate this tree and transform it as needed. Because only the unoptimised tree is stored, I felt there was no need to store this twice (doing so would also increase the size of PPU files)."

This copy of the tree is stored for inline functions before the first pass is executed.  Pure functions copy and analyse the same tree.  If a function is both pure and inline, these initial trees will always be identical, so it is redundant to store two copies.

Kit