[fpc-devel] Progress on pure functions

[J. Gareth Moreton]

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

On 14/12/2022 10:18, Sven Barth via fpc-devel wrote:
> J. Gareth Moreton via fpc-devel <fpc-devel at lists.freepascal.org> 
> schrieb am Di., 13. Dez. 2022, 22:09:
>
>     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
>        pc2start:=@s[1];
>        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).
>
>
> 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
>
> _______________________________________________
> fpc-devel maillist  -fpc-devel at lists.freepascal.org
> https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freepascal.org/pipermail/fpc-devel/attachments/20221214/21bff0b2/attachment.htm>