[fpc-devel] Prototype optimisation... Sliding Window

[J. Gareth Moreton]

That's useful to know, thanks.  Ideally I'd like to put it behind a kind 
of CSE compiler flag because this will add a degree of overhead to it 
and make compilation slower (currently I'm only doing it for -O3).  
Currently I'm only tracking "mov (ref),%reg" and "lea (ref),%reg" 
instructions and will build from there.

You know I'm never one to turn down a challenge - honestly I'm surprised 
I got this much success already!

I'll take a look at your commits.  At present, to ensure mistakes are 
not made, the sliding window is emptied/reset whenever the following is hit:

- A live label.
- An instruction that modifies the stack pointer (this one may prove 
unnecessary due to register tracking).
- An instruction that writes to memory, since even if it writes to the 
stack or global memory, there's no way to fully predict whether another 
register is pointing to this location and is hence volatile.

Gareth aka. Kit

On 17/02/2022 21:38, Jonas Maebe via fpc-devel wrote:
> On 17/02/2022 20:25, J. Gareth Moreton via fpc-devel wrote:
>> P.S. The term "sliding window" comes from the LZ77 compression 
>> algorithm and is used to track repeated sequences in ZIP files, among 
>> others. This prototype optimisation essentially uses the same 
>> construct, but built for instructions instead of individual bytes.
>
> The usual term for this kind of optimisations is common subexpression 
> elimination (CSE). We used to have one at the assembler level for i386 
> (my first main contribution to the compiler), but removed it in the 
> end because it was extremely prone to breaking — even more so than the 
> peephole optimiser. This happened in 
> a04cae2c4ba32bc5c7a8461b5851dee8e70c272b (it was supposed to have 
> happened in 1b439307490861afd739ba5a48dc175f09727a89, but I made a 
> mistake).
>
> It doesn't mean it can't be implemented in a robust way, but I can 
> guarantee from experience that it is extremely hard.
>
>
> Jonas
> _______________________________________________
> fpc-devel maillist  -  fpc-devel at 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