From patchwork Fri Jun 3 17:32:04 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Jelinek X-Patchwork-Id: 629954 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3rLrl055Ccz9t6k for ; Sat, 4 Jun 2016 03:32:28 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=qxP/7+45; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:cc:subject:message-id:reply-to:mime-version :content-type; q=dns; s=default; b=IqbYUgnhliffiUY0aLcz32HZ/nJVa N6kgV5XAjTaXOiitSaz38D5qcVL4hFh/F1ev1XyrFUBSuGHIc5q/5r/owXC+aN39 GbFq/1DF7P7O7xJDqNY4q46cV1kyPTnd2UZTcGxhMBZ3SkHUdx2xoA7Ck3/+5PyU wRg8Ru6NXHp2Lo= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:cc:subject:message-id:reply-to:mime-version :content-type; s=default; bh=TxFEoKg5Kxe4oTfyfGPxi2tD6XI=; b=qxP /7+45MEv3gkkgYF/n/JTwXCtG5G4+bcYbpTb/E7TQE6/a2y7Hq2rqFPkbcb1UAVM fBNuZpPdT94DqP7pgkAiMfWN4RDrCPop+WRUpzJkbb2rzOG15PblClu4gCF2I4Er uJNEVLcFH2zgZ5BxBzTlO+nNjEkapU6hVOfa6HQU= Received: (qmail 8509 invoked by alias); 3 Jun 2016 17:32:20 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 8477 invoked by uid 89); 3 Jun 2016 17:32:19 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-3.3 required=5.0 tests=BAYES_00, RP_MATCHES_RCVD, SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=df, d.f X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-GCM-SHA384 encrypted) ESMTPS; Fri, 03 Jun 2016 17:32:09 +0000 Received: from int-mx10.intmail.prod.int.phx2.redhat.com (int-mx10.intmail.prod.int.phx2.redhat.com [10.5.11.23]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 2FD9763E1E for ; Fri, 3 Jun 2016 17:32:08 +0000 (UTC) Received: from tucnak.zalov.cz (ovpn-116-51.ams2.redhat.com [10.36.116.51]) by int-mx10.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id u53HW68e028354 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=NO); Fri, 3 Jun 2016 13:32:07 -0400 Received: from tucnak.zalov.cz (localhost [127.0.0.1]) by tucnak.zalov.cz (8.15.2/8.15.2) with ESMTP id u53HW51I032059; Fri, 3 Jun 2016 19:32:05 +0200 Received: (from jakub@localhost) by tucnak.zalov.cz (8.15.2/8.15.2/Submit) id u53HW4iB032058; Fri, 3 Jun 2016 19:32:04 +0200 Date: Fri, 3 Jun 2016 19:32:04 +0200 From: Jakub Jelinek To: Jason Merrill Cc: gcc-patches@gcc.gnu.org Subject: [C++ PATCH] Avoid exponential compile time in cp_fold_function (PR c++/70847, PR c++/71330, PR c++/71393) Message-ID: <20160603173204.GL7387@tucnak.redhat.com> Reply-To: Jakub Jelinek MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.24 (2015-08-30) X-IsSubscribed: yes Hi! As mentioned in these PRs, if there are many nested SAVE_EXPRs or TARGET_EXPRs and many of those appear two or more times in the tree, cp_fold_function has huge compile time requirements. Even when each cp_fold should use a cache and once something has been folded, will return the same tree again and again, even just walking the same huge trees over and over and doing the cache lookups over and over takes lots of time. The following patch fixes it by making sure that during a single cp_fold_function, we recurse on the subtrees of each cp_fold returned tree once, not more. Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? 2016-06-03 Jakub Jelinek Patrick Palka PR c++/70847 PR c++/71330 PR c++/71393 * cp-gimplify.c (cp_fold_r): Set *walk_subtrees = 0 and return NULL right after cp_fold call if cp_fold has returned the same stmt already in some earlier cp_fold_r call. (cp_fold_function): Add pset automatic variable, pass its address to cp_walk_tree. * g++.dg/opt/pr70847.C: New test. * g++.dg/ubsan/pr70847.C: New test. * g++.dg/ubsan/pr71393.C: New test. Jakub --- gcc/cp/cp-gimplify.c.jj 2016-06-02 18:35:18.000000000 +0200 +++ gcc/cp/cp-gimplify.c 2016-06-03 15:23:47.098894612 +0200 @@ -940,6 +940,17 @@ cp_fold_r (tree *stmt_p, int *walk_subtr *stmt_p = stmt = cp_fold (*stmt_p); + if (((hash_set *) data)->add (stmt)) + { + /* Don't walk subtrees of stmts we've already walked once, otherwise + we can have exponential complexity with e.g. lots of nested + SAVE_EXPRs or TARGET_EXPRs. cp_fold uses a cache and will return + always the same tree, which the first time cp_fold_r has been + called on it had the subtrees walked. */ + *walk_subtrees = 0; + return NULL; + } + code = TREE_CODE (stmt); if (code == OMP_FOR || code == OMP_SIMD || code == OMP_DISTRIBUTE || code == OMP_TASKLOOP || code == CILK_FOR || code == CILK_SIMD @@ -997,7 +1008,8 @@ cp_fold_r (tree *stmt_p, int *walk_subtr void cp_fold_function (tree fndecl) { - cp_walk_tree (&DECL_SAVED_TREE (fndecl), cp_fold_r, NULL, NULL); + hash_set pset; + cp_walk_tree (&DECL_SAVED_TREE (fndecl), cp_fold_r, &pset, NULL); } /* Perform any pre-gimplification lowering of C++ front end trees to --- gcc/testsuite/g++.dg/opt/pr70847.C.jj 2016-06-03 11:44:13.507026612 +0200 +++ gcc/testsuite/g++.dg/opt/pr70847.C 2016-06-03 11:43:22.000000000 +0200 @@ -0,0 +1,11 @@ +// PR c++/70847 +// { dg-do compile } + +struct D { virtual D& f(); }; + +void +g() +{ + D d; + d.f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f(); +} --- gcc/testsuite/g++.dg/ubsan/pr70847.C.jj 2016-06-03 11:47:13.862624882 +0200 +++ gcc/testsuite/g++.dg/ubsan/pr70847.C 2016-06-03 11:43:22.000000000 +0200 @@ -0,0 +1,11 @@ +// PR c++/70847 +// { dg-do compile } + +struct D { virtual D& f(); }; + +void +g() +{ + D d; + d.f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f(); +} --- gcc/testsuite/g++.dg/ubsan/pr71393.C.jj 2016-06-03 11:35:55.675656051 +0200 +++ gcc/testsuite/g++.dg/ubsan/pr71393.C 2016-06-03 11:35:26.000000000 +0200 @@ -0,0 +1,14 @@ +// PR c++/71393 +// { dg-do compile } +// { dg-options "-fsanitize=undefined" } + +struct B { B &operator << (long); }; +struct A { A (); long a, b, c, d, e, f; }; + +A::A () +{ + B q; + q << 0 << a << 0 << b << 0 << (b / a) << 0 << c << 0 << (c / a) << 0 + << d << 0 << (d / a) << 0 << e << 0 << (e / a) << 0 << f << 0 + << (f / a) << 0; +}