So I got my salvaged code transferred over, now I'm mostly researching
the constant propagation and inlining code. I may have to make
adjustments to the constant propagation code so i can reuse it, so I can
introduce things like a node counter (to catch infinite loops) as well
as allow the use of TCallNode (I'll probably just modify the structure
that the 'arg' parameter points to so it can contain flags and a counter
and the like).
The one I'm still working out theoretically is determining if processing
the pure function this way has actually yielded a straightforward result
and not some complex node tree. Ideally, it should be just a simple
tree that writes the answer to the temporary result storage (and any
'out' parameters that exist, although given this approach, it might work
with 'var' parameters as well in some situations). If it's a more
complex tree that manipulates variables, then it should reject it and
just call the function conventionally (and throw a compiler warning to
indicate the function is not pure).
There is one other situation where a function might be pure but not
inline... if the function is so large that making it inline is extremely
wasteful, but is otherwise technically a pure function and will give a
deterministic result for a given input. An example might be a function
that calcuates a MacLaurin series in order to produce a result of the
desired precision.
Gareth aka. Kit
On 02/05/2020 20:55, J. Gareth Moreton wrote:
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
