[llvm-bugs] [Bug 32142] New: After r287232, excessively long compile times for Skein hash code (partially unrolled)

[via llvm-bugs]

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

            Bug ID: 32142
           Summary: After r287232, excessively long compile times for
                    Skein hash code (partially unrolled)
           Product: new-bugs
           Version: trunk
          Hardware: PC
                OS: All
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: new bugs
          Assignee: unassignedbugs at nondot.org
          Reporter: dimitry at andric.com
                CC: llvm-bugs at lists.llvm.org

Created attachment 18053
  --> https://bugs.llvm.org/attachment.cgi?id=18053&action=edit
Preprocessed skein_block.c test case

After importing clang 4.0.0 (branches/release_40 296509) to FreeBSD-CURRENT, I
got reports from several people that skein_block.c, an implementation of the
Skein hash block function
(https://github.com/freebsd/freebsd/blob/master/sys/crypto/skein/skein_block.c),
was taking extremely long to compile, compared to clang 3.9.1.

I bisected for this slowdown, and found that this revision causes it:
------------------------------------------------------------------------
r287232 | dfukalov | 2016-11-17 17:07:52 +0100 (Thu, 17 Nov 2016) | 12 lines

[SCEV] limit recursion depth of CompareSCEVComplexity

Summary:
CompareSCEVComplexity goes too deep (50+ on a quite a big unrolled loop) and
runs almost infinite time.

Added cache of "equal" SCEV pairs to earlier cutoff of further estimation.
Recursion depth limit was also introduced as a parameter.

Reviewers: sanjoy

Subscribers: mzolotukhin, tstellarAMD, llvm-commits

Differential Revision: https://reviews.llvm.org/D26389
------------------------------------------------------------------------

The attached test case, which is preprocessed and standalone, can be used to
show this.  On an Intel(R) Xeon(R) CPU E5-2630 v3 @ 2.40GHz, with trunk
r287231:

$ time ~/obj/llvm-trunk-r287231/bin/clang -cc1 -triple x86_64 -S -O2
-vectorize-loops -vectorize-slp skein_block.c
        3.41 real         3.35 user         0.05 sys

With trunk r287232:

$ time ~/obj/llvm-trunk-r287232/bin/clang -cc1 -triple x86_64 -S -O2
-vectorize-loops -vectorize-slp skein_block.c
       85.76 real        85.67 user         0.08 sys

E.g a factor 25 slowdown!  This effect persists in recent trunk, where it is
even a little worse:

$ time ~/obj/llvm-trunk-r296986/bin/clang -cc1 -triple x86_64 -S -O2
-vectorize-loops -vectorize-slp skein_block.c
       87.22 real        87.14 user         0.07 sys

Reverting r287232 on trunk r296986 also fixes the excessive compile time:

$ time ~/obj/llvm-trunk-r296986-287232/bin/clang -cc1 -triple x86_64 -S -O2
-vectorize-loops -vectorize-slp skein_block.c
        3.52 real         3.45 user         0.07 sys

In short, I'm not sure which bug r287232 was supposed to fix, but apparently it
makes compilation performance much worse in some cases.

For FreeBSD this a blocker for 4.0.0, so I'm going to back it out locally, but
I think it should also be backed out in the official 4.0.0 release.  Of course,
unless somebody can find a way to really fix this. :)

-- 
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/20170305/4522e3bf/attachment-0001.html>