Hi everyone,

So as my optimisations get more and more sophisticated and intelligent, I'm realising that I may need ways to store more information than is currently possible.  Obviously I want to avoid enlarging the internal state too much or making the code unwieldly, but the additions I have in mind are for tai objects:

- A connected tai object
- A flags field or some kind of weighting field

The connected tai object would be useful for jumps that branch to labels that were created during peephole optimisation, since these can't be looked up with "getlabelwithsym" and so lose out on some subsequent optimisations that look across jumps.

In regards to the weighting, a flag that indicates "desire to delete" or something similar would be very useful in deciding if temporarily making the code worse will have a larger payoff later on.  Consider the following code snippet (in the Classes unit under -O4 during some of my personal experimentation):

    ...
    movq    %rdx,%rsi
    movq    %r8,%rdi
    testq    %r8,%r8
    je    .Lj2408
    call    CLASSES$_$TFPLIST_$__$$_COPYMOVE$TFPLIST     movq    %rdi,%rdx
    jmp    .Lj2409
    .p2align 4,,10
    .p2align 3
.Lj2408:
    movq    %rsi,%rdx
.Lj2409:
    movq    %rbx,%rcx
    call    CLASSES$_$TFPLIST_$__$$_MERGEMOVE$TFPLIST     ...

There's an option to insert "cmoveq %rsi,%rdx", mirroring the "movq %rsi,%rdx" instruction (between the two labels), before "je .Lj2408", and change that conditional branch to "je .Lj2409".  By itself, this wouldn't be a good optimisation because CMOV is slightly slower than MOV and it would break the macrofusion betwen the TEST and JE instructions, as well as increasing code size and overall instruction count.  However, it would cluster the two labels and .Lj2408 only has a single reference; if it and the MOV instruction were removed, the entire block between "jmp .Lj2409" and its label would collapse, erasing the original MOV, and then a subsequent pass will notice that "cmoveq %rsi,%rdx" is unnecessary because %rdx = %rsi already at that point in the program flow, thus restoring the macrofusion.  At this point, the optimal code would be:

    ...
    movq    %rdx,%rsi
    movq    %r8,%rdi
    testq    %r8,%r8
    je    .Lj2409
    call    CLASSES$_$TFPLIST_$__$$_COPYMOVE$TFPLIST     movq    %rdi,%rdx
    .p2align 4,,10
    .p2align 3
.Lj2409:
    movq    %rbx,%rcx
    call    CLASSES$_$TFPLIST_$__$$_MERGEMOVE$TFPLIST     ...

Given that .Lj2409 only has a single reference from the nearby conditional branch, it may be beneficial to remove the alignment hints at this point too, although that one is more up in the air. Nevertheless, if the peephole optimizer, while scanning the conditional jump, sees that the destination label only has a single reference and has been flagged 'desire to delete', it will be more likely to perform the optimisation.  However, if the flag is clear, it won't optimise.  As for when to set that flag, it will probably be when the peephole optimizer scans the original "jmp .Lj2409" instruction and sees how close it is to being a zero distance jump, with only alignment fields, another label and a single MOV before it finds .Lj2409.

I'm aware that the tai class declares an "optinfo" field, although I'm uncertain if this is safe to use or not given it's wrapped by an conditional define and is of type Pointer.  I could use optinfo to store a reference to the tai_label object in a jump instruction - would this be an acceptable use of it?  I'm not sure about using it for a 'desire to delete' flag though, especially where there might be situations where other tai objects could carry it... maybe even a jump instruction.

This is more of a running commentary of my design thoughts, so I apologise for the info dump, but to summarise, could I add a 'connected object' and 'flags' field to the tai class, and/or can I use the optinfo field for a similar purpose?

Remember I can always refactor later if a feature could be cleaned up or restructured in some way.

Gareth aka. Kit

J. Gareth Moreton wrote

I'm aware that the tai class declares an "optinfo" field, although I'm uncertain if this is safe to use or not given it's wrapped by an conditional define and is of type Pointer.

It's wrapped under {$ifndef NOOPT}, because it's intended for use by assembler optimisers and when NOOPT is defined, no assembler optimisers are included.

It's defined as pointer because it's a field of an abstract base class in a unit that has no dependencies on target-specific units, and the actual type could be different for different target architectures.

Its purpose is indeed to attach a pointer to a record with extra information that is only collected/updated during the optimisation phase.

Jonas

That's useful to know - thanks Jonas.

One drawback I've noticed is that there's no clean way to free the optinfo pointer when the tai object is destroyed, plus there's the danger of the pointer being used as a plain integer instead of pointing to an actual structure (conversely, the Tag property in components was often used to hold an object pointer, especially in the 32-bit days).  I would like to propose having a Boolean field named "OwnsOptInfo" that, if True, calls Dispose on optinfo's value in tai's destructor so we don't get memory leaks.

Gareth aka. Kit

J. Gareth Moreton wrote

One drawback I've noticed is that there's no clean way to free the optinfo pointer when the tai object is destroyed,

The best way to handle this is by allocating the optinfo's from a pool (linked list of more or less arrays of whatever your TOptinfo type is), storing the pointers to the pool entries in the field, and free the entire pool in one go when done. Don't bother with freeing entries of removed instructions to reuse for added instructions, since not that many instructions get added and that would result in extra complexity and overhead for very little memory gain.

plus there's the danger of the pointer being used as a plain integer instead of pointing to an actual structure

Such a change to the compiler would/should never be accepted.

Jonas

That seems fair - thanks for the advice Jonas.  Now I just have to decide where best to store this linked list of records. I'm sensing the best place would be the TAsmOptimizer object that gets created and released with each procedure that's optimised, if I remember correctly.

Gareth aka. Kit

Would you approve something like this, Jonas?  I admit it's not properly tested yet, but I'm descending from TLinkedListItem (and the descendant class can itself be descended from) and the TAOptObj class handles allocation and cleanup of extra information.  I'm not sure how practical it is, but I'm taking advantage of the linked list system by allowing tai objects to have more than one extra information object associated with it.

https://gitlab.com/CuriousKit/optimisations/-/compare/main...opt-info-list?from_project_id=29565238

I hope you can view it!

It might be worth changing the defintion of optinfo from Pointer to TExtraOptInfo (the TLinkedListItem descendant), but I don't know if this may break something that's already present.

One thing I did miss was a "typ" field for TExtraOptInfo so you can look up to see what kind of object it is without relying on ClassType etc, but I don't know where and how to define such an enumeration because the different types would be platform-dependent.  All I can think of currently is an include file for each platform, which comes with its own problems.

Gareth aka. Kit

Just made some more additions, this time introducing some fundamental extra optimisation information classes that I can see myself using right off the bat.

https://gitlab.com/CuriousKit/optimisations/-/compare/main...opt-info-list?from_project_id=29565238

I plan to use the tai one for pointing jumps to labels, a simple Boolean one for flagging potential label removals in some optimisations that may be difficult to justify without such information (see some of my previous e-mails) and the Register/value pair for tracking known register values.

Gareth aka. Kit

One for Jonas mainly, but also for Florian.  This is a new "extra optimisation information" feature that allows the peephole optimizer to leave 'notes' and other extra information on individual tai objects for later reference.  An initial showcase is to store a link to the destination label if it's not available in the lookup table (becuase it was created later by a peephole optimisation).

https://gitlab.com/freepascal.org/fpc/source/-/merge_requests/74/diffs

Currently the showcase doesn't appear to show any additional optimisations in the x86-64 RTL because the jump optimisation that creates a new label is almost never called.

I'll use this feature more extensively in the future, such as for storing information on the values of registers or making a note of a label that should be removed if possible because it would cause a long-term optimisation (something that a peephole optimisation that removes the label may not be able to determine because its own optimisation is questionable without that information).  See previous e-mails in this chain for an example.

Gareth aka. Kit

I fear a little bit that this extra info is messed up when instructions are added/removed.

That's why I was discussing with Jonas in how to handle that, since currently tai objects don't have a clean way to free them themselves, and optinfo is an untyped Pointer.  However, Jonas suggested to have the extra info objects stored in a linked list, so the solution I have in my showcase is a linked list owned by the TAsmOptimizer object that frees everything when it's destroyed.  If an instruction is added or destroyed, the extra info objects associated with remain in the linked list, just not attached to anything.  True, there would be dangling pointers left in them, but they're solely for searching purposes and they generally aren't dereferenced.  You need a valid tai object to access the relevant extra info.

Granted, it would be cleaner to simply have the extra opt accessed through a new field in the tai declaration, and the constructor and destructor handle initialisation and cleanup.

Gareth aka. Kit

I do hope we can find an acceptable proposal.  I'm finding other potential uses for such extra information that can't really be replicated in the optimiser any other way, or it will take prohibitively long to do so (e.g. on the order of O(n²)).  For example, take this assembly snippet:

    addl    $1,%edi
    movq    -264(%rbp),%rax
    movl    %edi,%edx
    movq    56(%rax,%rdx,8),%rax
    (%rdx deallocated)

At the moment, the optimiser cannot make this any better, but as humans, we can note that the upper 32 bits of %rdi are zero because of the ADD instruction, and so improved code would be:

    addl    $1,%edi
    movq    -264(%rbp),%rax
    movq    56(%rax,%rdi,8),%rax

(Note that even if %edi wasn't used later, we can't merge the ADD instruction into the reference because of what happens if %edi = $FFFFFFFF before the ADD instruction)

Currently, the compiler cannot do this optimisation automatically because while it evaluates "movl %edi,%edx", the peephole optimizer doesn't know about the state of %rdi - for all it knows, the upper 32 bits could be non-zero.  A solution could be for the ADD instruction to search ahead for the next MOV instruction that uses its output register and store extra information there to indicate that the upper 32 bits are definitely zero.  There might be other solutions to this particular optimisation, like extending the capabilities of register-tracking objects, although i don't know how practical this really is.

A deeper example might be to help track dependency chains to help the compiler make more informed long-distance optimisations. Currently, I'm improving some of the optimisations made by OptPass2ADD and OptPass2SUB under -O3 in the name of breaking dependency chains, which can span a fair few instructions. However, there are a few cases where it grows the code size without improving speed.  For example:

    addl    $1,%edi
    movq    16(%rbx),%rax
    movq    8(%rax),%rcx
    movl    %edi,%edx

Under my improvements, which are beneficial in most places, this will change to the following:

    leal    1(%edi),%edx
    addl    $1,%edi
    movq    16(%rbx),%rax
    movq    8(%rax),%rcx

Because of the dependency chain between "movq 16(%rbx),%rax" and "movq 8(%rax),%rcx" along with using another AGU, this sequence will still take 2 cycles to execute at best (not counting latency from memory accesses).  Better insight into the dependency chain and the execution ports used might tell the compiler not to make the optimisation in this case.

Heh, this is starting to delve beyond simple logic and into the realm of machine learning if I'm not careful!

Gareth aka. Kit