Hi everyone,

So after my x86_64 optimizer overhaul was rejected in its current form, I decided to set to work again in cleaner steps.  The first thing I've started to address are jump optimisations, since they gave notable improvements that were independent of things lke the reduction in the number of passes.  There is also a bonus... a lot of it is cross-platform too!

One thing I do need to do is to cross-compile to all known platforms... I can only test a handful of the i386 and x86_64 platforms, but I want to at least see if it compiles before I submit the patch for more thorough testing.  Does anyone have any tips or a sample script (preferably a .BAT file) that cross-compiles from x86_64-win64 or i386-win32 onto a reasonable set of platforms that at least gives me a good smoke test? (Obviously, every combination is a little overkill if impractical).

I'm trying to keep things as simple as possible, but for the best optimisations, I had to introduce a new function for all platforms:

*function *condition_in(*const *c1, c2: TAsmCond): Boolean;

It is similar to "conditions_equal", but it returns true if c1 is a subset of c2 (e.g. "C_E" and "C_L" are both subsets of "C_LE", but "C_LE" is not a subset of "C_L").  It always returns True if c2 is "C_None" (i.e. an unconditional jump) or if the conditions are equal, but analysing the subsets is platform-specific.  I've done the best I can for the platform-specific assemblers that I don't know too well, but I'll need someone to check them over and maybe improve them, since I don't know what some of the conditions are.  The function is mostly failsafe, in that if it returns False, an optimisation won't be performed.  It's to help track final jump destinations more accurately, as well as detect what I call 'dominated jumps' - for example:

jbe @lbl1
je   @lbl2

The je instruction will never branch because the jbe instruction above it will branch if the equality condition is met, so it can be safely removed.

I'll run the win32 and win64 tests over Thursday and will submit the patches once everything passes, as well as a PDF design and implementation spec to explain what everything is as well as the concepts of dominated jumps and the like.

Gareth aka. Kit

A partial example of where "condition_in" shows its power (compiled code from fpc\packages\fcl-base\src\advancedipc.pp)

BEFORE:

    ...
    jb    .Lj178
    subl    $17,%eax
    cmpl    $26,%eax
    jb    .Lj178
    cmpl    $30,%eax
    stc
    je    .Lj178
    subl    $32,%eax
    cmpl    $26,%eax
.Lj178:
    jc    .Lj180    (Appears later in the code)     ...

AFTER:

    ...
    jb    .Lj180    <-- Label changed
    subl    $17,%eax
    cmpl    $26,%eax
    jb    .Lj180    <-- Label changed
    cmpl    $30,%eax
    stc
    je    .Lj178
    subl    $32,%eax
    cmpl    $26,%eax
.Lj178:
    jc    .Lj180    (Appears later in the code)     ...

In this case, 'condition_in' detects that C_C is a subset of C_B (they're actually equivalent in this case... both branch if the Carry Flag is set).  This particular optimisation means that the code only has to branch once if the JB conditions are met, rather than twice.

Gareth aka. Kit

If you only want to test whether the compiler builds you can do a "fullcycle" inside the compiler directory.

If you also want to test whether the RTL compiles you could use dummyas in compiler\utils and pass that as AS and compile the RTL for all platforms you want to test though that will obviously hide assembly problems. Otherwise you'll need binutils for all platforms you want to test.

I myself (as I'm using Windows 10) use the Windows Subsystem for Linux where I have installed the binutils for various targets and can compile the whole of FPC from the same repository I use on Windows for various targets and using QEMU's user space emulation I can even run the testsuite.

Regards,
Sven

I forgot about "fullcycle", thanks.  The main reason is because of the "condition_in" functions I've added to the other platforms - I want to see if they at least compile!

Now the fun begins.

Gareth aka. Kit

So the tests all passed on i386-win32 and x86_64-win64, so that's s a good sign.  I can't submit the patches for evaluation yet because I haven't finished the design spec yet, and also because of a minor bug that deals with collapsing label clusters:

    .p2align 4,,10
    .p2align 3
.Lj370:
.Lj367:
.Lj364:
.Lj361:
.Lj358:
.Lj355:
.Lj352:
.Lj349:
.Lj346:
.Lj343:
.Lj340:

In this segment, everything is stripped except for the last label, which is fine as all the references are changed too. Unfortunately, the alignment fields are removed too, which shouldn't happen.  It doesn't produce incorrect code, but it may incur a performance penalty, so shouldn't be removed - I'm just trying to figure out why that's happening!

Gareth aka. Kit

J. Gareth Moreton schrieb am Fr., 1. Nov. 2019,
12:56:

Considering that you said that this feature is essentially cross platform: on some other platform the alignments might be important beside performance (e.g. a branch inside a branch delay slot or something like that). So, yeah, that should be fixed...

Regards,
Sven

Turns out it wasn't a bug, but a very contrived set-up.

When the peephole optimiser is turned off completely, the following is revealed:

    je    .Lj371
    jmp    .Lj372
.Lj371:
    movl    $3,%r14d
    movl    $1,%r15d
    jmp    .Lj373
    .p2align 4,,10
    .p2align 3
.Lj372:
    jmp    .Lj333
.Lj373:
.Lj370:
.Lj367:
   ...

What happens is that the optimiser changes "je .Lj371; jmp .Lj372; .Lj371:" into "jne .Lj372" (what I call a 'conditional jump inversion'), and then the final destination is tracked: the compiler notices that after "jne .Lj372", the program flow immediately stumbles upon an unconditional jump ("jmp .Lj333"), so it changes the destination to match, thus it becomes "jne .Lj333".  After all of this, .Lj372 becomes a dead label, and when the optimiser reaches "jmp .Lj373", it removes all the dead code between it and the next live label, since it will never be executed; this includes the original "jmp .Lj333" instruction because .Lj372 is no longer referenced by anything (Then "jmp .Lj373" is removed as well because the destination label is right after it once everything is stripped).  As such, because .Lj372 is a dead label and there are no other (live) labels in that cluster, it correctly removes the alignment fields... in other words, the remaining labels were never actually aligned - it was just a coincidence they became aligned before.

Gareth aka. Kit

Jump optimisation patches ready, and something resembling a design spec to explain things.

https://bugs.freepascal.org/view.php?id=36271

Gareth aka. Kit

Made some more updates to the jump optimisation patches, removing code duplication and also some untidy debugging code.

Gareth aka. Kit

Is there anything I should do to aid testing the jump optimisations, or is there anything else that needs cleaning up?

Unfortunately there are "TODO" comments in some of the "condition_in" functions because I don't know enough about that particular platform to ensure correctness, but it is failsafe in that it will simply return False after trying a simple comparison (calls "conditions_equal") and checking against the trivial 'C_None'.

I do wonder if I'm allowed to override the "in" operator so the code that calls those functions is a bit cleaner.

Gareth aka. Kit