[llvm-bugs] [Bug 27110] New: Degraded speed of generated output

[via llvm-bugs]

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

            Bug ID: 27110
           Summary: Degraded speed of generated output
           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: llvm-bugs at lists.llvm.org
    Classification: Unclassified

Created attachment 16116
  --> https://llvm.org/bugs/attachment.cgi?id=16116&action=edit
demo source code

I found there was a serious speed degrade for the output of clang when
compiling some specific kind of code since two weeks ago.

The attached file is a solver for 8-queen puzzle, it can be compiled with:

/opt/bin/clang -std=c99 -mssse3 -O3 -fomit-frame-pointer -fno-stack-protector
-fno-exceptions -o 8 8.c

Currently in my machine, it took 2.52s to run with eight queens:

$ time ./8 9                                                                    
352 solutions
./8 9  2.52s user 0.01s system 99% cpu 2.545 total

But about two weeks ago, it took only ** 2.20s ** to finish the same input.

What is interesting is in the following function:

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;
}

Changing it to:

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;
}

could reduce the time from 2.52s to 2.31s (9% boost).

I checked the output assembly of gcc-5.3 and Intel compiler 2016.2, they both
did the optimization which splits the judgement statement to:

            if (a[i] == a[j]) return 0;
            const int p = a[i] - a[j];
            if (p == -x || p == -x) return 0;

but clang didn't do this. If I manually rewrite the code, it took 2.15s (15%
boost).

---------

Comparing to gcc-5.3:

$ /opt/bin/gcc -std=c99 -mssse3 -O3 -fomit-frame-pointer -fno-stack-protector
-fno-exceptions -o 8 8.c
$ time ./8 9                                                                    
352 solutions
./8 9  2.04s user 0.01s system 99% cpu 2.069 total

and Intel compiler 2016.2:

$ icc -std=c99 -mssse3 -O3 -fomit-frame-pointer -fno-stack-protector
-fno-exceptions -o 8 8.c                                
$ time ./8 9                                                                    
352 solutions
./8 9  2.07s user 0.00s system 99% cpu 2.077 total

-- 
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/20160329/e28c3cb6/attachment.html>