[Bug rtl-optimization/67396] [4.9/5.0 regression] Performance regression compiling variadic function with many arguments

["miyuki at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

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

Mikhail Maltsev <miyuki at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|x86_64-*-*                  |
                 CC|                            |miyuki at gcc dot gnu.org
            Version|5.2.0                       |unknown
   Target Milestone|4.9.4                       |---
            Summary|[4.9/5/6 regression]        |[4.9/5.0 regression]
                   |Performance regression      |Performance regression
                   |compiling variadic function |compiling variadic function
                   |with many arguments in RTL  |with many arguments
                   |DSE                         |

--- Comment #7 from Mikhail Maltsev <miyuki at gcc dot gnu.org> ---
(In reply to Paul Pluzhnikov from comment #5)

> for j in 500 1000 2000 3000; do perl ./gen_bz18872.pl $j > t.c ; (time
> gcc-svn-r227326-rel/bin/gcc -c -O2 t.c) |& grep user; done
> 
> user	0m1.488s
> user	0m12.010s
> user	1m40.353s
> user	5m47.668s

Rough fitting suggests that it is O(n^3).

I did some profiling and it looks like we get rather deep recursion in alias
analysis. Most time is spent in the following call chain: dse_step1 ->
scan_insn -> record_store -> canon_true_dependence -> true_dependence1. It has
2 callees, which start deep recursion: memrefs_conflict_p and find_base_term
(the latter is invoked twice, the profiler suggests that only the second call,
i.e.

rtx mem_base = find_base_term (true_mem_addr);

is a hot spot). Then we start to recur via these 2 (interleaving) calls:

      f = val->locs;
      /* Temporarily reset val->locs to avoid infinite recursion.  */
      val->locs = NULL;

      for (l = f; l; l = l->next)
        if (GET_CODE (l->loc) == VALUE
            && CSELIB_VAL_PTR (l->loc)->locs
            && !CSELIB_VAL_PTR (l->loc)->locs->next
            && CSELIB_VAL_PTR (l->loc)->locs->loc == x)
          continue;
        else if ((ret = find_base_term (l->loc)) != 0)

1865            else if ((ret = find_base_term (l->loc)) != 0)
(gdb) p l->loc
$6 = (rtx_def *) (plus:DI (value:DI 2:4321 @0x1abc518/0x1ab8a20)
    (const_int -8 [0xfffffffffffffff8]))


and:

        /* Go ahead and find the base term for both operands.  If either base
           term is from a pointer or is a named object or a special address
           (like an argument or stack reference), then use it for the
           base term.  */
        rtx base = find_base_term (tmp1);
        if (base != NULL_RTX
            && ((REG_P (tmp1) && REG_POINTER (tmp1))
                 || known_base_value_p (base)))
          return base;

#1  0x000000000062b92a in find_base_term (x=<optimized out>) at
/home/miyuki/gcc/src/gcc/alias.c:1917
1917            rtx base = find_base_term (tmp1);
(gdb) p tmp1
$7 = (rtx_def *) (value:DI 2:4321 @0x1abc518/0x1ab8a20)

It's harder to say what happens in memrefs_conflict_p because it is
tail-recursive. This function has ~20 calls of itself. Perhaps basic block
profiling will tell more.

P.S. The profiler shows an estimate: alias.c:get_addr is invoked ~300000000
times (that is for 1000 printf arguments).
>From gcc-bugs-return-495959-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Mon Aug 31 09:24:43 2015
Return-Path: <gcc-bugs-return-495959-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 9005 invoked by alias); 31 Aug 2015 09:24:42 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 8947 invoked by uid 48); 31 Aug 2015 09:24:39 -0000
From: "ro at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug bootstrap/67363] [6 Regression] r227188 breaks build for mingw-w64
Date: Mon, 31 Aug 2015 09:24:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: bootstrap
X-Bugzilla-Version: 6.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: ro at gcc dot gnu.org
X-Bugzilla-Status: NEW
X-Bugzilla-Resolution:
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: dmalcolm at redhat dot com
X-Bugzilla-Target-Milestone: 6.0
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: bug_status cf_reconfirmed_on cc everconfirmed
Message-ID: <bug-67363-4-1Y2863e9aS@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-67363-4@http.gcc.gnu.org/bugzilla/>
References: <bug-67363-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2015-08/txt/msg02101.txt.bz2
Content-length: 726

https://gcc.gnu.org/bugzilla/show_bug.cgi?idg363

Rainer Orth <ro at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2015-08-31
                 CC|                            |ro at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #4 from Rainer Orth <ro at gcc dot gnu.org> ---
Right: using xstrndup instead of strndup is the right fix and matches other
parts
of the gcc directory.  This patch also broke Solaris 10 bootstrap.

I'll later commit that fix as obvious.

  Rainer