[LLVMbugs] [Bug 23016] New: a==-b and -a==b runs at different speed

[bugzilla-daemon at llvm.org]

https://llvm.org/bugs/show_bug.cgi?id=23016

            Bug ID: 23016
           Summary: a==-b and -a==b runs at different speed
           Product: clang
           Version: trunk
          Hardware: PC
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: LLVM Codegen
          Assignee: unassignedclangbugs at nondot.org
          Reporter: 191919 at gmail.com
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified

The following C code is a 8-queen puzzler solver for educational purpose.

#include <stdio.h>
#include <stdlib.h>

static inline int validate(const int* a, const int d)
{
        for (int i = 0; i < d; ++i)
        {
                for (int j = i + 1, x = 1; j < d; ++j, ++x)
                {
                        const int p = a[i] - a[j];
                        ///////////// !!!!!!!!!!
                        if (p == 0 || p == x || p == -x) return 0;
                }
        }
        return 1;
}

static inline int solve(int d)
{
        int r = 0;
        int* a = (int*) calloc(sizeof(int), d+1);
        int p = d - 1;

        for (;;)
        {
                a[p]++;

                if (a[p] > d-1)
                {
                        int bp = p - 1;
                        while (bp >= 0)
                        {
                                a[bp]++;
                                if (a[bp] <= d-1) break;
                                a[bp] = 0;
                                --bp;
                        }
                        if (bp < 0)
                                break;
                        a[p] = 0;
                }
                if (validate(a, d))
                {
                        ++r;
                }
        }

        free(a);
        return r;
}

int main(int argc, char** argv)
{
    if (argc != 2) return -1;
        int r = solve((int) strtol(argv[1], NULL, 10));
        printf("%d solutions\n", r);
}

In function `validate`, there is a line:

                        if (p == 0 || p == x || p == -x) return 0;

If I compile the source without any modifications and run it:

$ /opt/bin/clang -v
clang version 3.7.0 (trunk 233173)
Target: x86_64-apple-darwin14.1.0
Thread model: posix

$ /opt/bin/clang -O3 -o 8 8.c
$ time ./8 9
352 solutions
./9 9  1.96s user 0.00s system 99% cpu 1.966 total

Now I change that line to:

                        if (p == 0 || p == x || -p == x) return 0;

then compile with the same command line and run it again:

$ /opt/bin/clang -O3 -o 8 8.c                                                   
$ time ./8 9                 
352 solutions
./8 9  1.84s user 0.00s system 99% cpu 1.845 total

As you see, there I got a 7% speed boost by just swapping the left and right
side of an equation.

The weirder thing is if I compile the same source code with clang-3.5 which
comes with Xcode 6.1.3 or 6.2, the result flipped:

$ clang -v
Apple LLVM version 6.0 (clang-600.0.57) (based on LLVM 3.5svn)
Target: x86_64-apple-darwin14.1.0
Thread model: posix

# original
$ clang -O3 -o 8 8.c     # p == x || p == -x
$ time ./8 9
352 solutions
./8 9  1.98s user 0.00s system 99% cpu 1.982 total

$ clang -O3 -o 8 8.c     # p == x || -p == x
$ time ./8 9
352 solutions
./9 9  1.66s user 0.00s system 99% cpu 1.658 total

The speed difference is nearly 17%.

I am really confused how the optimizer works and can't stop to worry if I have
to manually try to swap all the equations of my codes to get faster codes.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20150325/7cf8afaa/attachment.html>