Hi everyone,

I've found a potential optimisation for conditions of the form "(x 0) and (y 0)", which are very common because this is semantically equivalent to "Assigned(x) and Assigned(y)", for example, and such a construct is generated implicity in TObject.Destroy, for example.  The node tree for TObject.Destroy example (after the first pass) is as follows (it checks the value of Self and VMT):

The node tree inside the if-node's condition branch is as follows:

<andn resultdef="Boolean" pos="329,9" flags="nf_pass1_done" complexity="3">    <unequaln resultdef="Boolean" pos="329,9" flags="nf_pass1_done" complexity="1">
      <loadn resultdef="TObject" pos="329,9" flags="nf_pass1_done" complexity="0">
         <symbol>self</symbol>
      </loadn>
      <niln resultdef="TObject" pos="329,9" flags="nf_pass1_done" complexity="0">
      </niln>
   </unequaln>
   <unequaln resultdef="Boolean" pos="329,9" flags="nf_pass1_done" complexity="1">
      <typeconvn resultdef="$char_pointer" pos="329,9" flags="nf_pass1_done,nf_explicit,nf_internal" complexity="0" convtype="tc_equal">
         <typeconvn resultdef="Pointer" pos="329,9" flags="nf_pass1_done" complexity="0" convtype="tc_equal">             <loadn resultdef="&lt;no type symbol&gt;" pos="329,9" flags="nf_pass1_done" complexity="0">
               <symbol>vmt</symbol>
            </loadn>
         </typeconvn>
      </typeconvn>
      <pointerconstn resultdef="$char_pointer" pos="329,9" flags="nf_pass1_done,nf_explicit" complexity="0">
         <value>$0000000000000000</value>
      </pointerconstn>
   </unequaln>
</andn>

On x86-64_win64, the following assembly language is generated (smart pipelining and out-of-order execution MIGHT permit it to be executed in 3 cycles, but it's more likely going to take 4 or 5):

    testq    %rbx,%rbx
    setneb   %al
    testq    %rsi,%rsi
    setneb   %dl
    andb     %dl,%al

DeMorgan's Laws for 2 inputs state that "not (A or B) = not A and not B", and "not (A and B) = not A or not B", and using these, we can develop much more efficient assembly language (which will almost certainly take 3 cycles to run, and is much smaller):

    movq     %rbx,%rdx
    orq      %rsi,%rdx
    seteb    %al

For this particular routine, %rsi and %dl/%rdx are not used afterwards, and can be simplified further (this bit will probably be a peephole optimisation), dropping the cycle count to 2:

    orq      %rbx,%rsi
    seteb    %al

In this situation it is safe because the comparison values are already in registers and code generation has permitted the bypassing of Boolean short-circuiting.

Rather than write an entire peephole optimisation, I would ideally like to program this optimisation at the nodal level, and permit the compiler to convert it into something resembing the following ("andn" becomes "notn" -> "orn", and the two "unequaln" nodes become "equaln"):

<notn resultdef="Boolean" pos="329,9" flags="nf_pass1_done" complexity="3">    <orn resultdef="Boolean" pos="329,9" flags="nf_pass1_done" complexity="3">
      <equaln resultdef="Boolean" pos="329,9" flags="nf_pass1_done" complexity="1">
         <loadn resultdef="TObject" pos="329,9" flags="nf_pass1_done" complexity="0">
            <symbol>self</symbol>
         </loadn>
         <niln resultdef="TObject" pos="329,9" flags="nf_pass1_done" complexity="0">
         </niln>
      </equaln>
      <equaln resultdef="Boolean" pos="329,9" flags="nf_pass1_done" complexity="1">
         <typeconvn resultdef="$char_pointer" pos="329,9" flags="nf_pass1_done,nf_explicit,nf_internal" complexity="0" convtype="tc_equal">
            <typeconvn resultdef="Pointer" pos="329,9" flags="nf_pass1_done" complexity="0" convtype="tc_equal">                <loadn resultdef="&lt;no type symbol&gt;" pos="329,9" flags="nf_pass1_done" complexity="0">
                  <symbol>vmt</symbol>                </loadn>
            </typeconvn>
         </typeconvn>
         <pointerconstn resultdef="$char_pointer" pos="329,9" flags="nf_pass1_done,nf_explicit" complexity="0">
            <value>$0000000000000000</value>          </pointerconstn>
      </equaln>
   </orn>
</notn>

...but there is a catch.  In terms of the raw nodes, converting the "andn" node into a "notn" and an "orn" node results in a more complex node tree and hence less efficient assembly language in general, unless a particular "pass_generate_code" routine knows to look out for the set-up of a logical "or" that combines two variables' comparison against zero, like that shown above.

My question is... how should it be developed so that the node optimisation is performed on platforms that have the necessary assembly instructions, like x86_64 and AArch64 (once I develop them), but also not perform the optimisation on platforms that don't have the necessary instructions or checks in "pass_generate_code"?  Allowing the optimisation wouldn't cause bad code generation, but it would be more inefficient in the general case.

I hope I explained that okay.

(Other possibilities include introducing new node types "norn" and "nandn" (and maybe "nxorn" to complete the set), and having the "andn" node above be converted into "norn", so that they can be instantly converted into the relevant assembly instructions instead of relying on multiple steps of optimistion)

Gareth aka. Kit

You can introduce a new pass in the compiler, that does the node transformation only on platforms that benefit from it. See e.g. what I did a few years ago in optloadmodifystore.pas in the compiler sources. This is an optimization that introduces new nodes that generate faster code on x86 for patterns, such as:

a := a + b

Which can be done with a single 'add mem, const' or 'add mem, reg' instruction on all processors in the x86 family (i8086, i386 and x86_64). Also, I think there were other CPUs that benefit from this optimization (m68k?). For that, I introduced new inline compiler nodes, that are only used for this optimization.

Introducing norn and nand for optimization purposes might not be a bad idea, considering there are some CPU architectures that also have nor and nand instructions (powerpc, for example).

Best regards,

Nikolay

P.S. I don't think we need "WARNING: Technical!" trigger warnings on fpc-devel ;-)

I am not sure how this is equal:

consider rbx=1, esi=1: current code results in al=1; the last sample results in al=0. Or do I miss something?

Due to DeMorgan's Laws (not A and not B = not (A or B)) I'd say that this should be "setneb %al".

Regards,
Sven

Yes, so we get "not((x=0) or (y=0))". But this does not translate to "not(x or y)".

Rats, I might have messed up with some of the arithmetic, as well as the dangers of crossing bitwise with logical Boolean operations, although some combinations still work - if the conditions are "x = 0" rather than "x 0" in the example:

     testq    %rbx,%rbx
     seteb    %al
     testq    %rsi,%rsi
     seteb    %dl
     andb     %dl,%al

Then this would equate to:

     orq      %rbx,%rsi
     seteb    %al

And if a conditional jump follows the "set" instruction, then this could be removed as well.  Of course, implementing the optimisation would have revealed my little arithmetic mistake there.

(A 0) and (B 0) = not((A = 0) or (B = 0)), but what I wrote before effectively calculated (A or B) 0. Thanks for spotting my error, Florian.

Mistake aside, I'm looking for acceptable solutions for a platform-dependent node transformation, like a flag of some kind ($if defined etc. might get untidy, although is an option).

Gareth aka. Kit

Indeed:

# [6] b:=(x=0) and (y=0);
orl %edx,%eax
# Var b located in register al
seteb %al

:)

This depends on the transformation. Most transformations are beneficial for all platforms.

Suddenly I'm feeling embarrassed!  I'll have to look up to see how that one is optimised!

I'll look around to see if there are other possible optimisations that revolve around DeMorgan's Laws first.  For "b:=(x0) and (y0);", there might not be a simple transformation available after all because, generally, bitwise not logical not.  The main question regarding transformations is that there might be a place for "nor" and "nand" operations (more traditional operations for electronics since you can make circuits that do all the basic Boolean operations using just NOR and NAND gates... e.g. a NAND gate where both inputs are wired to the same signal becomes a NOT gate), and Intel does have "and not" (ANDN) as a single instruction on later processors (anything that supports BMI1).

Gareth aka. Kit

I am pretty sure we miss some of the bit fiddeling stuff listed here: https://en.wikipedia.org/wiki/Bitwise_operation#Boolean_algebra

But there are more, like (typical pattern in the sha algorithm, I think I have even an unfinished patch for this one):

(a and b) or (c and not(b)) => c xor ((c xor a) and b)

One operation less and no additional temp. needed. Some googling might reveal more.

Those can be done normally one the fly during code generation,