[Bug rtl-optimization/72855] New: Long compile time due to integrity checking during dataflow analysis per loop

[wschmidt at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=72855

            Bug ID: 72855
           Summary: Long compile time due to integrity checking during
                    dataflow analysis per loop
           Product: gcc
           Version: 5.4.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: wschmidt at gcc dot gnu.org
  Target Milestone: ---

Created attachment 39091
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=39091&action=edit
C++ file showing excessive compile time

This was reported to me for the gcc compilers on Ubuntu 14.04 and 16.10, and
occurs on all compilers from GCC 4.8 through current trunk.  A partial
backtrace shows:

#0  df_ref_equal_p (ref1=0x1000fca3c40, ref2=0x1000d2e0570)
    at /home/wschmidt/gcc/gcc-mainline-base/gcc/df-scan.c:2045
#1  0x0000000010647a00 in df_ref_equal_p (ref2=0x1000d2e0570, 
    ref1=<optimized out>)
    at /home/wschmidt/gcc/gcc-mainline-base/gcc/df-scan.c:2041
#2  df_refs_verify (new_rec=0x3fffddb13f30, old_rec=0x1000d2e0570, 
    abort_if_fail=true)
    at /home/wschmidt/gcc/gcc-mainline-base/gcc/df-scan.c:4030
#3  0x000000001064e518 in df_insn_refs_verify (collection_rec=0x3fffddb13f30, 
    bb=0x3fffa0baf908, insn=0x3fff98487340, abort_if_fail=true)
    at /home/wschmidt/gcc/gcc-mainline-base/gcc/df-scan.c:4113
#4  0x000000001064eca0 in df_bb_verify (bb=0x3fffa0baf908)
    at /home/wschmidt/gcc/gcc-mainline-base/gcc/df-scan.c:4142
#5  0x0000000010652fa8 in df_scan_verify ()
    at /home/wschmidt/gcc/gcc-mainline-base/gcc/df-scan.c:4274
#6  0x0000000010635404 in df_verify ()
    at /home/wschmidt/gcc/gcc-mainline-base/gcc/df-core.c:1830
#7  df_analyze_1 () at /home/wschmidt/gcc/gcc-mainline-base/gcc/df-core.c:1216
#8  0x000000001091ced0 in iv_analysis_loop_init (loop=0x3fff9ef663e0)
    at /home/wschmidt/gcc/gcc-mainline-base/gcc/loop-iv.c:285
#9  0x0000000011309d98 in doloop_optimize (loop=0x3fff9ef663e0)
    at /home/wschmidt/gcc/gcc-mainline-base/gcc/loop-doloop.c:624
#10 doloop_optimize_loops ()

This is where we spend the lion's share of 2 hours of compilation time for the
attached example.  Using -fno-checking on GCC 6 drops the compilation time to 7
minutes on a POWER8 with lots of memory.  However, this workaround is not
available on earlier compiler versions.  Note that the Ubuntu compilers are
built with --enable-checking=release.

The test case does (far too) aggressive inlining which creates a large function
with many loops.  It appears that iv_analysis_loop_init calls df_analyze_loop
for each loop, which causes df_verify to be run over the whole function many
times.  It's not that efficient to begin with, so...

Given the nature of the problem, reducing the test case isn't very practical,
and since the only headers are from libstdc++, I've provided the
un-preprocessed code (which is much smaller due to all the macro expansion). 
To reproduce:

$ gcc -std=gnu++1y -O3 --param early-inlining-insns=200 -c ltc144607.cpp

This is very similar to a problem Richard looked at before: 
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=38518.  Something similar should
probably be done to try to limit how often the df_analyze code is called.