Note that I speak mostly from an x86_64 perspective, since this is where I have almost universal exposure.

So I've been pondering a few things after researching Florian's prototype patch for optimisations done prior to register allocation, when the pre-compiled assembly language utilises imaginary (virtual) registers pretty much everywhere other than where distinct registers are required (e.g. function parameters).  My question is... how much can be moved to the pre-allocation stage?  I believe it can make the outcome far more efficient, especially with my initial work on the deep optimizer as a few people have stated already.  Unless I'm mistaken, from what I've observed, a lot of the peephole optimizations don't actually care what registers they're playing with.

There are also situations in optimization where one might detect a repeat calculation that the programmer cannot eliminate themselves, but which the best optimization is to store the result and re-use it later... the most obvious situation where this arises is with div and mod with the same numerator and denominator.  Currently, the compiler doesn't know any better and has to calculate the division twice, a relatively expensive operation, even though DIV returns both the quotient and the remainder in RAX and RDX respectively.  I believe storing the mod result in a virtual register for later use will be far easier to manage when the registers have not yet been allocated, especially if it's determined that a new register has to be preserved in the function prologue, or there are no free registers at all and it has to be put on the stack, or if it's at all possible to use RDX itself as that temporary storage (the most ideal outcome in both speed and size), something that would be near impossible if RDX has been allocated for something in between.

Speaking of the deep optimizer, I do have a patch ready to submit once the backlog of other patches are analysed (it relies on a few of them), and I'll be working on porting elements of it to the pre-allocation stage.  Some bits are a little difficult because of how imaginary registers are tracked... if you delete an instruction, you have to be careful you don't leave a dangling pointer in the "live range".

This is just thinking out loud and pondering.
Gareth aka. Kit

A lot, basically everything which reduced register pressure. The only problem is, at this stage, the code contains a lot of moves (compile with -sr to see how it looks like). So the optimizer must be able to handle this. It might be even possible to build a generic optimizer pass at this stage. Example:

A typical sequence FPC often generates is:

mov %src1,%dest1
add %dest1,%src2,%dest2

If src1 is no released after mov but dest1 is release, src1 and dest1 still cannot be coalesced as they interfere, so an extra register is allocated. The move will be remove by the peephole optimizer, but register was allocated and increase register pressure. Such optimizations could be done generic (for all CPUs): if the destination of a mov is only read afterwards (this information is already generically available), the mov can be removed and in this case dest1 can be replaced by src1.

The penalty for separate div & mod operations for your scenario is severe on targets that require software implementation (e.g. 8 bit AVR). There is a DivMod implementation in unit math, would be useful if this is available in system.

Indeed, so if it can be done only once, that's a major saving.  Even if div and mod are separate assembler instructions on the target platform, it's possible to make a saving if multiplication and subtraction aren't too expensive, as then the modulus can be calculated via r = n - qd.

The issue with DivMod is that the saving isn't that great because of the penalty of calling a subroutine, which amounts to around 50 cycles on x86-64, about equal to DIV.  This could be alleviated if the function is able to be inlined or, when dealing with constants, can be identified as a 'pure' function (I wrote a little request article about this: http://wiki.freepascal.org/Feature_Ideas#.22pure.3B.22_function_directive [1] )

Gareth aka. Kit

On Sun 17/06/18 10:08 , "Christo Crause" sent:
The penalty for separate div border-left:1px #ccc solid;padding-left:1ex">

There are also situations in optimization where one might detect a repeat calculation that the programmer cannot eliminate themselves, but which the best optimization is to store the result and re-use it later... the most obvious situation where this arises is with div and mod with the same numerator and denominator.  Currently, the compiler doesn't know any better and has to calculate the division twice, a relatively expensive operation, even though DIV returns both the quotient and the remainder in RAX and RDX respectively.  I believe storing the mod result in a virtual register for later use will be far easier to manage when the registers have not yet been allocated, especially if it's determined that a new register has to be preserved in the function prologue, or there are no free registers at all and it has to be put on the stack, or if it's at all possible to use RDX itself as that temporary storage (the most ideal outcome in both speed and size), something that would be near impossible if RDX has been allocated for something in between.
Gareth aka. Kit

That's where the first stage of my deep optimizer might be able to help, since it explicitly starts at a MOV command (say, mov %reg_source, %reg_dest) and scans forward to see if %reg_dest can be replaced with %reg_source - it stops when it hits a jump, call, non-skippable label, when the registers change value or if %reg_dest cannot be replaced.  If all references to %reg_dest were replaced prior to its value being completely overwritten, then it can then delete the original MOV.

While it will only be appropriate to run at -O2 and -O3, the restrictions surrounding the register replacement, and specially where it stops searching, help ensure that it runs relatively quickly. Find attached a test patch of the deep optimizer - it was intertwined with a number of other peephole changes, so I hope these were removed successfully and won't cause a compiler error.  (This is what I intend to submit to the bug reporter as a patch eventually)  Running the compiler with DEBUG_AOPTCPU enabled will show where the deep optimizer has made savings in the .s files.

Gareth aka. Kit

On Sun 17/06/18 09:56 , Florian Klämpfl sent:

J. Gareth Moreton wrote

Note that I speak mostly from an x86_64 perspective, since this is where

I have almost universal exposure.

So I've been pondering a few things after researching Florian's

prototype patch for optimisations done prior to register

allocation, when the pre-compiled assembly language utilises imaginary

(virtual) registers pretty much everywhere other

than where distinct registers are required (e.g. function parameters). 

My question is... how much can be moved to the

pre-allocation stage?

A lot, basically everything which reduced register pressure. The only problem is, at this stage, the code contains a lot of moves (compile with -sr to see how it looks like). So the optimizer must be able to handle this. It might be even
possible to build a generic optimizer pass at this stage. Example:

A typical sequence FPC often generates is:

mov %src1,%dest1
add %dest1,%src2,%dest2

If src1 is no released after mov but dest1 is release, src1 and dest1 still cannot be coalesced as they interfere, so an extra register is allocated. The move will be remove by the peephole optimizer, but register was allocated and increase register pressure. Such optimizations could be done generic (for all CPUs): if the destination of a mov is only read
afterwards (this information is already generically available), the mov can be removed and in this case dest1 can be
replaced by src1.

Florian Klämpfl schrieb am So., 17. Juni 2018,
10:56:

Though only if the type of src1 is the same as that of dest1, right? (e.g. int vs. address register)

Regards,
Sven

Aah, I was in error. I used agner as my source, but even that says 5 cycles for a near call and 17-33 for a far call, so I'm not sure where I got 50 from. My apologies. I have probably been avoiding function calls more than necessary!

Gareth aka. Kit

On Sun 17/06/18 18:06 , David Pethes sent:
Hi,

J. Gareth Moreton wrote

The issue with DivMod is that the saving isn't that great because of the penalty of calling a subroutine, which amounts to around 50 cycles on x86-64, about equal to DIV.

That number sounds awfully high, what's your source?

David

That's where the first stage of my deep optimizer might be able to help, since it explicitly starts at a MOV command (say, mov %reg_source, %reg_dest) and scans forward to see if %reg_dest can be replaced with %reg_source - it stops when it hits a jump, call, non-skippable label, when the registers change value or if %reg_dest cannot be replaced.  If all references to %reg_dest were replaced prior to its value being completely overwritten, then it can then delete the original MOV.

While it will only be appropriate to run at -O2 and -O3, the restrictions surrounding the register replacement, and specially where it stops searching, help ensure that it runs relatively quickly. By the way, now that the debug strip patch has now being approved (thanks Florian!), I can now safely submit my prototype for the Deep Optimizer! https://bugs.freepascal.org/view.php?id=33871 - as specifid in the notes, compile the compiler with the DEBUG_AOPTCPU directive and compile projects with the -a flag if you wish to see where the Deep Optimizer has made savings in the intermediate assemblies.

Note that this version works during post-peephole optimisations.  I'm looking at ways to move it to the preallocation phase in a way that's extensible, especially in regards to tracking virtual registers.  It's a little tricker because it's very easy to leave a dangling pointer.

Gareth aka. Kit

On Sun 17/06/18 09:56 , Florian Klämpfl sent:

J. Gareth Moreton wrote

Note that I speak mostly from an x86_64 perspective, since this is where

I have almost universal exposure.

So I've been pondering a few things after researching Florian's

prototype patch for optimisations done prior to register

allocation, when the pre-compiled assembly language utilises imaginary

(virtual) registers pretty much everywhere other

than where distinct registers are required (e.g. function parameters). 

My question is... how much can be moved to the

pre-allocation stage?

A lot, basically everything which reduced register pressure. The only problem is, at this stage, the code contains a lot of moves (compile with -sr to see how it looks like). So the optimizer must be able to handle this. It might be even
possible to build a generic optimizer pass at this stage. Example:

A typical sequence FPC often generates is:

mov %src1,%dest1
add %dest1,%src2,%dest2

If src1 is no released after mov but dest1 is release, src1 and dest1 still cannot be coalesced as they interfere, so an extra register is allocated. The move will be remove by the peephole optimizer, but register was allocated and increase register pressure. Such optimizations could be done generic (for all CPUs): if the destination of a mov is only read
afterwards (this information is already generically available), the mov can be removed and in this case dest1 can be
replaced by src1.

Ignore my last e-mail - I sent it yesterday and thought the attachment was too big (it's also slightly faulty).  See here instead: https://bugs.freepascal.org/view.php?id=33871

Gareth

Aah, okay. Thanks Tomas.
It turns out the patch had a couple of faults anyway - thanks for letting it through though.  I can never guarantee the size of .patch files. Gareth

On Mon 18/06/18 16:02 , "Tomas Hajny" sent:

J. Gareth Moreton wrote

Ignore my last e-mail - I sent it yesterday and thought the attachment was too big (it's also slightly faulty).  See here instead: https://bugs.freepascal.org/view.php?id=33871 [1]

It was indeed held for moderation due to its size. Since it wasn't much bigger compared to the limit, I decided to let it through.

Tomas (one of FPC mailing list moderators)

J. Gareth Moreton wrote

Ignore my last e-mail - I sent it yesterday and thought the attachment was too big (it's also slightly faulty).  See here instead: https://bugs.freepascal.org/view.php?id=33871

It was indeed held for moderation due to its size. Since it wasn't much bigger compared to the limit, I decided to let it through.

Tomas (one of FPC mailing list moderators)

I figured this is as good a place as any to talk about my attempt at improving the speed of the stage 1 optimizer in issue #33855.  On paper, a binary search is the fastest method to locate a data pointer associated with a key (in this case, an opcode).  Of course, in practice that isn't always the case due to overhead and the penalties (or lack of) associated with conditional jumps.
The main problem with my binary search implementation is the extra complexity it puts into the code, and as Markov mentioned, the fact it's limited to just x86 rather than being more general-purpose.  The ideal solution is to tie the binary search and the associated key/data map into the compiler, specifically the case node generation, but there are some theoretical issues that need to be resolved:
- What is the minimum number of case nodes where a binary search should be used over a simpler linear search?  The maximum number of iterations of a binary search loop is equal to ceil(log2(n)), where n is the size of the list.  Further optimisations with the likes of CMOVcc and loop unrolling can eliminate jumps entirely, but there is still significant overhead where it might be faster to simply perform a linear search, especially where the most frequent entry is at or near the top of the list.
- How can it be detected that each case node has an identical setup?  With the optimizer, the current opcode is passed through a case block, and if a match is found, it is passed through an object method of the format "function(var p: tai): Boolean".  The fact that the function calls are identical means that some optimisation can be performed with common sub-expressions, specifically passing the address of p into RDX or RSI, depending on if the OS is Windows or Linux on x86-64.
- What happens if there is an imperfection in the source code? A vague question, I know, but in the case, some of the functions are of the format "function(const p: tai): Boolean", which require a slightly different set-up with the parameters.  This is not an error, and the functions are sometimes set up this way if p never changes (which is the case if this particular instruction is never deleted by the optimizer), but it breaks the homogenuity of the case nodes and hence would make a highly-optimized search much harder.  Should the programmer be warned or given a hint in how to improve their code, or is it up to us to be smart enough to spot "const p: tai" instead of "var p: tai"?

- How easy would it be to make such a binary search more general-purpose? My particular code simply uses a map that pairs an opcode to a pointer in a many-to-one relationship.  In this case, the algorithm doesn't care what the pointer is - it could easily be a label address, an object or a generic block of memory on the heap instead of a procedural address.  Granted, as mentioned, the situation where each case node is a function call with an identical setup is a special case because jumps can be eliminated entirely. I think that's everything anyway.  I admit my motivations have slightly negative roots because I remember when the main advertising point of Turbo Pascal 7.0 was the speed of its compiler, and I'm harking back to those days.  Also the size of the binaries produced when compared to, say, Microsoft Visual C++.  Of course, size isn't as big of a concern as it was back in the days when you were limited to a 1.44 MB floppy disk, but if there's a space where I can eliminate or restructure inefficient or superfluous code, I'll take it!
If I can be filled in, how do case nodes work currently? I know there's a kind of linear search where the ordinal variable has a number subtracted that corresponds to the next case node, and something called a "jump table", but I'm not entirely sure how that works yet. Gareth aka. Kit

If I had to start somewhere though... this is an extract of the disassembly from the pass 1 optimizer from the SVN head:

x86_64aoptcpu.pas:105   result:=OptPass1OP(p);
488b16                   mov    (%rsi),%rdx 4889d9                   mov    %rbx,%rcx e8414f0000               callq  0x100189a30 4088c7                   mov    %al,%dil e951000000               jmpq   0x100184b48

90                       nop x86_64aoptcpu.pas:110   result:=OptPass1MOVXX(p); 4889f2                   mov    %rsi,%rdx 4889d9                   mov    %rbx,%rcx e8cd4c0000               callq  0x1001897d0 4088c7                   mov    %al,%dil eb40                     jmp    0x100184b48

x86_64aoptcpu.pas:112   result:=OptPass1LEA(p);
4889f2                   mov    %rsi,%rdx 4889d9                   mov    %rbx,%rcx e8ad500000               callq  0x100189bc0 4088c7                   mov    %al,%dil eb30                     jmp    0x100184b48

x86_64aoptcpu.pas:114   result:=OptPass1Sub(p);
4889f2                   mov    %rsi,%rdx 4889d9                   mov    %rbx,%rcx e89d580000               callq  0x10018a3c0 4088c7                   mov    %al,%dil eb20                     jmp    0x100184b48

There are some interesting things to note here.  OptPass1OP has "const p: tai" rather than "var p: tai" as a parameter, and this causes an unfortunate difference in the set-up, namely "mov (%rsi),%rdx" instead of "mov %rsi,%rdx".  If these were fixed  to all be "var p: tai" (I might actually do this, since it's a very simple change), then all the case nodes will be identical, save the call address, and would be a better experimental case for optimisation improvements.  Additionally, after the call, ther lies "mov %al,%dil" and an identical jump (to the end of the case block).  The MOV could easily be moved to after the jump with some careful code analysis, which might then allow for futher optimisation, depending on what is then done with %dil.

Gareth aka. Kit

J. Gareth Moreton wrote

On paper, a binary search is the fastest method to locate a data pointer associated with a key (in this case, an opcode).

Forgive me for stepping in, given that I hardly looked at your work, nor the particular part of fpc.
But the fastest way should be a hash look up (O(n) = 1)

I might have missed something, so maybe I am completely out of line....

You have an enum. This could be used as a hash key (no need to calculate, just take the raw value, and you have a perfect hash).

All you need to do is once build the hash table.
  lookup =  Array[tasmop] of CodePointer;
in unit initialization set the codepointer for the known opcodes.

Then you do not need to search. just
    codepointer := lookup[taicpu(p).opcode]

Actually you're right - that is the fastest method (it's written O(1), by the way, if it doesn't depend on n).  The drawback is that the large majority of instructions don't have such an optimisation procedure, so the table  would be extremely sparse.  There are 1,109 individual instructions on x86 that FPC currently supports.  Come to think of it, even that is not too bad as far as memory goes - you're looking at 8,872 bytes on i386 (4 bytes for the instruction and 4 bytes for a pointer) and 17,744 bytes on x86-64 (8 bytes for each field), both are potentially cacheable on the CPU hence won't be too costly in regards to looking it up.  Not sure why I overlooked that one.  Thanks Martin.

Gareth aka. Kit

On Mon 25/06/18 00:18 , Martin sent:

J. Gareth Moreton wrote

On paper, a binary search is the fastest method to locate a data pointer associated with a key (in this case, an opcode).

Forgive me for stepping in, given that I hardly looked at your work, nor the particular part of fpc.
But the fastest way should be a hash look up (O(n) = 1)

I might have missed something, so maybe I am completely out of line....

You have an enum. This could be used as a hash key (no need to calculate, just take the raw value, and you have a perfect hash).

All you need to do is once build the hash table.
  lookup =  Array[tasmop] of CodePointer;
in unit initialization set the codepointer for the known opcodes.

 Then you do not need to search. just
    codepointer := lookup[taicpu(p).opcode]

Of course, there's nothing to stop us from having a smaller table with an actual hash, but that may give too much constant overhead, especially a modulus operation.

Gareth aka. Kit

On Mon 25/06/18 04:23 , "J. Gareth Moreton"
sent:
Actually you're right - that is the fastest method (it's written O(1), by the way, if it doesn't depend on n).  The drawback is that the large majority of instructions don't have such an optimisation procedure, so the table  would be extremely sparse.  There are 1,109 individual instructions on x86 that FPC currently supports.  Come to think of it, even that is not too bad as far as memory goes - you're looking at 8,872 bytes on i386 (4 bytes for the instruction and 4 bytes for a pointer) and 17,744 bytes on x86-64 (8 bytes for each field), both are potentially cacheable on the CPU hence won't be too costly in regards to looking it up.  Not sure why I overlooked that one.  Thanks Martin.

Gareth aka. Kit

On Mon 25/06/18 00:18 , Martin sent:

J. Gareth Moreton wrote

On paper, a binary search is the fastest method to locate a data pointer associated with a key (in this case, an opcode).

Forgive me for stepping in, given that I hardly looked at your work, nor the particular part of fpc.
But the fastest way should be a hash look up (O(n) = 1)

I might have missed something, so maybe I am completely out of line....

You have an enum. This could be used as a hash key (no need to calculate, just take the raw value, and you have a perfect hash).

All you need to do is once build the hash table.
  lookup =  Array[tasmop] of CodePointer;
in unit initialization set the codepointer for the known opcodes.

 Then you do not need to search. just
    codepointer := lookup[taicpu(p).opcode]

In the meantime, I've just submitted this patch:
https://bugs.freepascal.org/view.php?id=33908 - it changes those routines with const p: tai to var p: tai.

Gareth aka. Kit

On Sun 24/06/18 23:12 , "J. Gareth Moreton"
sent:
If I had to start somewhere though... this is an extract of the disassembly from the pass 1 optimizer from the SVN head:

x86_64aoptcpu.pas:105   result:=OptPass1OP(p);
488b16                   mov    (%rsi),%rdx 4889d9                   mov    %rbx,%rcx e8414f0000               callq  0x100189a30 4088c7                   mov    %al,%dil e951000000               jmpq   0x100184b48

90                       nop x86_64aoptcpu.pas:110   result:=OptPass1MOVXX(p); 4889f2                   mov    %rsi,%rdx 4889d9                   mov    %rbx,%rcx e8cd4c0000               callq  0x1001897d0 4088c7                   mov    %al,%dil eb40                     jmp    0x100184b48

x86_64aoptcpu.pas:112   result:=OptPass1LEA(p);
4889f2                   mov    %rsi,%rdx 4889d9                   mov    %rbx,%rcx e8ad500000               callq  0x100189bc0 4088c7                   mov    %al,%dil eb30                     jmp    0x100184b48

x86_64aoptcpu.pas:114   result:=OptPass1Sub(p);
4889f2                   mov    %rsi,%rdx 4889d9                   mov    %rbx,%rcx e89d580000               callq  0x10018a3c0 4088c7                   mov    %al,%dil eb20                     jmp    0x100184b48

There are some interesting things to note here.  OptPass1OP has "const p: tai" rather than "var p: tai" as a parameter, and this causes an unfortunate difference in the set-up, namely "mov (%rsi),%rdx" instead of "mov %rsi,%rdx".  If these were fixed  to all be "var p: tai" (I might actually do this, since it's a very simple change), then all the case nodes will be identical, save the call address, and would be a better experimental case for optimisation improvements.  Additionally, after the call, ther lies "mov %al,%dil" and an identical jump (to the end of the case block).  The MOV could easily be moved to after the jump with some careful code analysis, which might then allow for futher optimisation, depending on what is then done with %dil.

Gareth aka. Kit

While probably not worth it, but if you want to save memory (and only few entries have data): Use 2 maps:

map1: array[opcode] of byte; // I do not know how efficient reading bytes is....
      maps the (hopefully fewer than 255 active entries)

map2: array[byte] of codepointer

One other problem with this method, and I think it has caused problems before - https://bugs.freepascal.org/view.php?id=32079 - is what happens if an invalid value is passed in for the opcode.  Granted, a sanity check can be employed.
One would need to develop some tight timing tests to determine the fastest method for a given number of cases.  As Florian once stated... it takes a large number of jumps before the standard linear subtraction search (where the ordinal difference is subtracted from each case branch in turn) becomes prohibitive.  On modern processors it can be as high as 64.

Gareth aka. Kit

On Mon 25/06/18 11:18 , Martin sent:
On 25/06/2018 05:23, J. Gareth Moreton wrote:
Actually you're right - that is the fastest method (it's written O(1), by the way, if it doesn't depend on n).  The drawback is that the large majority of instructions don't have such an optimisation procedure, so the table  would be extremely sparse.  There are 1,109 individual instructions on x86 that FPC currently supports.  Come to think of it, even that is not too bad as far as memory goes - you're looking at 8,872 bytes on i386 (4 bytes for the instruction and 4 bytes for a pointer) and 17,744 bytes on x86-64 (8 bytes for each field), both are potentially cacheable on the CPU hence won't be too costly in regards to looking it up.  Not sure why I overlooked that one.  Thanks Martin.

While probably not worth it, but if you want to save memory (and only few entries have data): Use 2 maps:

map1: array[opcode] of byte; // I do not know how efficient reading bytes is....
      maps the (hopefully fewer than 255 active entries)

map2: array[byte] of codepointer

How well does kcachegrind represent those timings?

Granted you don't want to run the entire compiler in kcachegrind, that might take very long. But if you extract the relevant code into a test/benchmark project, then that might help.