Avoid dependent FSQRT and FDIV where possible -freciprocal-math and -funsafe-math-optimizations

[ilinpv]

With the -freciprocal-math (and -funsafe-math-optimizations) the compiler can try harder to avoid dependent FSQRT and FDIV operations. For example

double res, res2, tmp;
void
foo (double a, double b, int c, int d)
{
  tmp = 1.0 / __builtin_sqrt (a);
  res = tmp * tmp;

  if (d)
    res2 = a * tmp;
}

With -Ofast aarch64 LLVM generates:

foo(double, double, int, int):                             // @foo(double, double, int, int)
        fsqrt   d1, d0
        fmov    d2, #1.00000000
        adrp    x8, tmp
        fdiv    d2, d2, d1
        str     d2, [x8, :lo12:tmp]
        fmul    d2, d2, d2
        adrp    x8, res
        str     d2, [x8, :lo12:res]
        cbz     w1, .LBB0_2
        fdiv    d0, d0, d1
        adrp    x8, res2
        str     d0, [x8, :lo12:res2]
.LBB0_2:
        ret

GCC at -Ofast can do:

foo(double, double, int, int):
        fmov    d1, 1.0e+0
        adrp    x0, .LANCHOR0
        fsqrt   d2, d0
        add     x2, x0, :lo12:.LANCHOR0
        fdiv    d0, d1, d0
        fmul    d1, d2, d0
        str     d0, [x2, 8]
        str     d1, [x0, #:lo12:.LANCHOR0]
        cbz     w1, .L1
        str     d2, [x2, 16]
.L1:
        ret

https://godbolt.org/z/jb8a14K16
Notice how the expensive FSQRT and FDIV are now independent and can execute in parallel.
A write-up of the transformation can be found in the GCC commit:
http://gcc.gnu.org/g:24c49431499bcb462aeee41e027a3dac25e934b3

[llvmbot]

@llvm/issue-subscribers-good-first-issue

[llvmbot]

@llvm/issue-subscribers-backend-aarch64

[chtnnh]

Hey @ilinpv !

I am someone who's interested in contributing to LLVM! Could you help me better understand this issue and how to proceed with resolving it?

What I understand now:

1. There are two expensive operations FSQRT and FDIV that are being generated to be executed sequentially
2. In some cases, they can be executed in parallel, like GCC does it
3. We need to refer GCC's implementation and make improvements to LLVM

This is my first bug, hopefully. So all help is welcome!

Thanks,
Chaitanya

[ilinpv]

Hi Chaitanya! Your understanding is correct. The sequences of sqrt reciprocal multiplications can be optimized so that division and sqrt operations become independent and 1 multiplication operation is saved.

t = sqrt (a);
tmp = 1.0 / t;
res1 = tmp * tmp;
res2 = a * tmp;

optimized into:

t = sqrt (a);
res1 = 1.0 / a;
res2 = t;
tmp = res1 * res2;

Gcc is just an example how this transformation was implemented in compiler which helps understanding.

[chtnnh]

Awesome!

I am taking up Compiler Construction at University this semester. According to my understanding so far, this will require a change in the Machine Independent Code Optimizations phase of the compiler. Could you point me to right directory in the source code to go about making these changes?

I will also take up any suggested reading, you might have in mind to better understand how to go about this patch.

Could you also assign this task to me, to allow me to begin work on this task?

Thanks a lot,
Chaitanya

[chtnnh]

I was digging through the llvm monorepo directory structure and trying to find what directory to look into.

Found some possible directories:

1. llvm-project/llvm/lib/Transforms
2. llvm-project/llvm/lib/Bitcode

Am I working in the right direction?

[ilinpv]

I think lib/CodeGen/SelectionDAG/DAGCombiner.cpp is a good starting point. Look into reciprocal and unsafe math transformations.

[ilinpv]

For reading, I would suggest code generator doc https://llvm.org/docs/CodeGenerator.html

[chtnnh]

@jcranmer-intel suggested i make the changes in llvm/lib/Transforms/InstCombine/

Where do you think I should proceed now?

[ilinpv]

Make sense to look into combine instructions pass as well. I think it would be better to make that transformations earlier in optimisations pipeline.