From patchwork Tue Nov 27 16:00:11 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paolo Bonzini X-Patchwork-Id: 202255 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]) by ozlabs.org (Postfix) with SMTP id 43EC22C0082 for ; Wed, 28 Nov 2012 03:01:31 +1100 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1354636892; h=Comment: DomainKey-Signature:Received:Received:Received:Received:From:To: Subject:Date:Message-Id:Mailing-List:Precedence:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:Sender: Delivered-To; bh=tD+Cp4j5/GdiillXXHTs7d35lKo=; b=R/HzQbrrYFS22EM +7faUW2Fcc/z89YBWO5GJ+0uV/BlHUtFdkNgd6pdDm5pK/9Q/J1MShJafaRf2lPN ptvvssZyy2Cp9P+TDDdycVfGJIUfVQgeYdGiS5d685/Kg7AwPgVRW9mX/u+jWiSu vxuudUvebmqjlE3rWuJh6FLMa8/0= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:From:To:Subject:Date:Message-Id:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=B0MfcUTxV0l/SyWfcfaEX17AtETnaoc03XvGhNf4JbxUcsUyC+H3yFblxPIdYg fb+qIbWoCKGfRvkEpjdPrzWLNyEG1hq1bUVWmms16+LfTlVCM8wDPrA2WtJAT5+f v5+J5osY/Hm3fly6KCSEBVS7kVWxp/uDnKwTKW/kpM3qw=; Received: (qmail 31376 invoked by alias); 27 Nov 2012 16:00:35 -0000 Received: (qmail 31089 invoked by uid 22791); 27 Nov 2012 16:00:31 -0000 X-SWARE-Spam-Status: No, hits=-6.5 required=5.0 tests=AWL, BAYES_00, KHOP_RCVD_UNTRUST, RCVD_IN_DNSWL_HI, RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from fencepost.gnu.org (HELO fencepost.gnu.org) (208.118.235.10) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 27 Nov 2012 16:00:22 +0000 Received: from bonzini by fencepost.gnu.org with local (Exim 4.71) (envelope-from ) id 1TdNa4-0001ZQ-NP for gcc-patches@gcc.gnu.org; Tue, 27 Nov 2012 11:00:16 -0500 From: Paolo Bonzini To: gcc-patches@gcc.gnu.org Subject: [PATCH] Fix PR55489, memory-hog bug in GCSE Date: Tue, 27 Nov 2012 17:00:11 +0100 Message-Id: <1354032011-32303-1-git-send-email-bonzini@gnu.org> 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 Hi, this bug triggers in the compilation of QEMU with GCC 4.7.2. It is latent on trunk because reg_known_value is completely broken. I'll send a separate patch, but this one applies there too. The problem arises when you have -fPIE (or -fPIC) and a huge function with a lot of references to global variables. Canonicalization of position-independent addresses is then done over and over for the same addresses, resulting in quadratic time and memory complexity for GCSE's compute_transp; hundreds of megabytes of memory are allocated in plus_constant, The fix is to canonicalize the addresses outside the loop, similar to what is done by the RTL DSE pass. gcc 4.4.6: PRE : 3.83 (24%) usr 0.15 (17%) sys 3.99 (24%) wall 267307 kB (33%) ggc gcc 4.7.2: PRE : 7.95 (41%) usr 0.40 (40%) sys 8.31 (41%) wall 821017 kB (80%) ggc gcc 4.8.0: PRE : 6.94 (26%) usr 0.02 ( 4%) sys 6.98 (26%) wall 731 kB ( 0%) ggc gcc 4.7.2 + patch: PRE : 5.90 (34%) usr 0.02 ( 3%) sys 6.41 (35%) wall 1670 kB ( 1%) ggc Note that the bug is present on older branches too, but it became much worse sometime between 4.4 and 4.7. Bootstrap finished on x86_64-pc-linux-gnu, regtest in progress; ok for 4.7 and trunk if it passes? Paolo 2012-11-26 Paolo Bonzini PR rtl-optimization/55489 * gcse.c (compute_transp): Precompute a canonical version of XEXP (x, 0), and pass it to canon_true_dependence. Index: gcse.c =================================================================== --- gcse.c (revisione 193848) +++ gcse.c (copia locale) @@ -1658,7 +1658,11 @@ compute_transp (const_rtx x, int indx, sbitmap *bm { bitmap_iterator bi; unsigned bb_index; + rtx x_addr; + x_addr = get_addr (XEXP (x, 0)); + x_addr = canon_rtx (x_addr); + /* First handle all the blocks with calls. We don't need to do any list walking for them. */ EXECUTE_IF_SET_IN_BITMAP (blocks_with_calls, 0, bb_index, bi) @@ -1683,7 +1687,7 @@ rtx dest_addr = pair->dest_addr; if (canon_true_dependence (dest, GET_MODE (dest), - dest_addr, x, NULL_RTX)) + dest_addr, x, x_addr)) RESET_BIT (bmap[bb_index], indx); } }