[fpc-devel] Progress on pure functions
J. Gareth Moreton
gareth at moreton-family.com
Thu Aug 17 11:46:27 CEST 2023
Getting there! I'm having one sticking point, and that's with pure
functions of the following design:
procedure Factorial(N: Cardinal; out R: Cardinal); pure;
begin
if N < 2 then
R := 1
else
begin
Factorial(N - 1, R);
R *= N;
end;
end;
Because of the recursive nature with the "out" parameter, it gets
flagged as "address taken" and, as a result, constant propagation will
not function. The deepest level of recursion works because it
essentially collapses into just "R := 1" and this can be inserted in
place of "Factorial(N - 1, R);" when N = 2, but constant propagation
refuses to go any further.
I can't modify the symtable because pure functions may have to be called
as regular functions (in the above example, if Factorial is called where
the actual parameter for N is a variable, it won't be analysed) so I'm
trying to work out if I can create a temporary procdef and symtable. So
far I haven't had much luck, but I'll keep up the work.
Kit
On 16/08/2023 05:05, J. Gareth Moreton via fpc-devel wrote:
> Fixed my problem with the recursive function (enabling range check and
> overflow errors blocked dead-store elimination, so I worked around
> that) and the warning no longer cascades. Progress is being made!
>
> Kit
>
> On 16/08/2023 04:02, J. Gareth Moreton via fpc-devel wrote:
>> So managed to stop the cascade in a fairly clean way (it detects the
>> difference in ErrorCount, marks the call node as erroneous and flags
>> "codegenerror"), and it seems to work.
>>
>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>> (6227020800 must be between -2147483648 and 2147483647)
>> pure1a.pp(15,24) Error: At least 1 error(s) occurred during the
>> purity analysis of subroutine "Factorial".
>> pure1a.pp(17) Fatal: There were 2 errors compiling module, stopping
>> Fatal: Compilation aborted
>>
>> The message says "at least X error(s)" because other errors may get
>> masked.
>>
>> My recursive version of the factorial function doesn't quite simplify
>> properly yet (it compiles successfully, but the call is a regular
>> call and a warning is generated):
>>
>> pure1b.pp(15,23) Warning: Subroutine "Factorial" is not eligible to
>> be a pure function due to the following reason: analysis did not
>> produce simple assignment.
>>
>> Being a warning, this cascades and is generated multiple times (the
>> number of times depends on how deep the recursion goes). I'll work on
>> suppressing the cascade too since when this warning is triggered, the
>> "pure" flag is removed from the subroutine.
>>
>> Currently the "analysis did not produce simple assignment" part is a
>> hard-coded string and not a part of errore.msg, for exmaple, so there
>> may need to be a way to adapt this to be multi-lingual.
>>
>> Kit
>>
>> On 12/08/2023 18:14, J. Gareth Moreton via fpc-devel wrote:
>>> Hi everyone,
>>>
>>> So I'm still working on pure functions and have pushed some merge
>>> requests that are indirectly related to it, mostly simplifying the
>>> node tree so it can more easily be collapsed into simple assignments
>>> (what pure functions should simplify to). Negative testing is still
>>> limited, but I have stumbled across one potential problem. Using
>>> the following code example:
>>>
>>> program pure1a;
>>> {$MODE OBJFPC}
>>> {$COPERATORS ON}
>>>
>>> function Factorial(N: Cardinal): Cardinal; pure;
>>> var
>>> X: Integer;
>>> begin
>>> Result := 1;
>>> for X := N downto 2 do
>>> Result *= X;
>>> end;
>>>
>>> begin
>>> WriteLn(Factorial(32));
>>> end.
>>>
>>> For those not familiar with the factorial function, the result
>>> increases in value very quickly to the point that 13! > 2^32
>>> (LongWord), 21! > 2^64 (QWord) and 70! > 10^100 (a googol), so 32!
>>> is guaranteed to overflow.
>>>
>>> Having not really handled this eventuality just yet, I decided to
>>> see what happens when the compiler runs it as is:
>>>
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (6227020800 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (27048749056 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (19184179200 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (32068960256 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (34071216128 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (-288522240 must be between 0 and 4294967295)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (4006445056 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (-5193400320 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (-898433024 must be between 0 and 4294967295)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (3396534272 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (-17070227456 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (-2102132736 must be between 0 and 4294967295)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (2192834560 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (-44144787456 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (-1195114496 must be between 0 and 4294967295)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (3099852800 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (-26292518912 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (-522715136 must be between 0 and 4294967295)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (3772252160 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (-12022448128 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (20698890240 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (-775946240 must be between 0 and 4294967295)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (3519021056 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (-19398656000 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (53980692480 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (-1853882368 must be between 0 and 4294967295)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (2441084928 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (-50054823936 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (41573941248 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (-1375731712 must be between 0 and 4294967295)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (2919235584 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (-39896219648 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (-1241513984 must be between 0 and 4294967295)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (3053453312 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (-37245419520 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (43687870464 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (23622320128 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Warning: Range check error while evaluating
>>> constants (-2147483648 must be between 0 and 4294967295)
>>>
>>> Not an ideal cascade of warnings. I figured it might be better to
>>> throw an error instead, so during the processing of pure functions,
>>> I enforced range and overflow checking:
>>>
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (6227020800 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (27048749056 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (19184179200 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (32068960256 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (34071216128 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (-288522240 must be between 0 and 4294967295)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (4006445056 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (-5193400320 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (-898433024 must be between 0 and 4294967295)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (3396534272 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (-17070227456 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (2192834560 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (-2102132736 must be between 0 and 4294967295)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (2192834560 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (-44144787456 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (-1195114496 must be between 0 and 4294967295)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (3099852800 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (-26292518912 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (-522715136 must be between 0 and 4294967295)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (3772252160 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (-12022448128 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (20698890240 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (-775946240 must be between 0 and 4294967295)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (3519021056 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (-19398656000 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (53980692480 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (-1853882368 must be between 0 and 4294967295)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (2441084928 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (-50054823936 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (41573941248 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (-1375731712 must be between 0 and 4294967295)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (2919235584 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (-39896219648 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (-1241513984 must be between 0 and 4294967295)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (3053453312 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (-37245419520 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (43687870464 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (23622320128 must be between -2147483648 and 2147483647)
>>> pure1a.pp(15,24) Error: Range check error while evaluating constants
>>> (-2147483648 must be between 0 and 4294967295)
>>> pure1a.pp(17) Fatal: There were 39 errors compiling module, stopping
>>> Fatal: Compilation aborted
>>>
>>> This is not much better and is very unhelpful and untidy in an error
>>> log. Since the node tree is expanded during pure function analysis
>>> (in this case, the for-loop is unrolled) and each node points to the
>>> function call, each compiler message thus points here. Ideally
>>> there should only be one warning/error message, but since these
>>> messages are generated elsewhere in the node compilation process,
>>> it's not that easy to catch it and drop out the instant an error is
>>> thrown.
>>>
>>> So to ask. If during analysis an overflow/range check error occurs,
>>> how do you think it should be handled? And does anyone have tips on
>>> how to program the compiler to immediately stop processing if a
>>> single error is found or to otherwise suppress subsequent messages
>>> that point to the same file location?
>>>
>>> Kit
>>>
>>> _______________________________________________
>>> fpc-devel maillist - fpc-devel at lists.freepascal.org
>>> https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
>>>
>> _______________________________________________
>> fpc-devel maillist - fpc-devel at lists.freepascal.org
>> https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
>>
> _______________________________________________
> fpc-devel maillist - fpc-devel at lists.freepascal.org
> https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
>
More information about the fpc-devel
mailing list