Re: [fpc-devel] Pure function development
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 On 02/05/2020 19:51, Jonas Maebe wrote: On 02/05/2020 20:27, J. Gareth Moreton wrote: 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. 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 ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel -- This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Pure function development
On 02/05/2020 20:27, J. Gareth Moreton wrote: > 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. 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 ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Pure function development
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 On 02/05/2020 18:51, Florian Klämpfl wrote: Am 01.05.20 um 11:41 schrieb J. Gareth Moreton: 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 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. 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. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel -- This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Pure function development
Am 01.05.20 um 11:41 schrieb J. Gareth Moreton: 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 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. 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. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[fpc-devel] r45217 breaks Lazarus compile
Compiling Lazarus trunk with the latest fpc: components/ideintf/propedits.pp(6019,28) Fatal: Internal error 200709171 Colin ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel