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@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@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
_______________________________________________
fpc-devel maillist - fpc-devel@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
