From patchwork Tue Jan 29 13:13:15 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 216531 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 1A5AC2C00DD for ; Wed, 30 Jan 2013 00:13:32 +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=1360070013; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Date: From:To:Subject:Message-ID:User-Agent:MIME-Version:Content-Type: Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:Sender:Delivered-To; bh=28afI6e54VaKdrkyUTgb epbL8MI=; b=qKKmcTlVEIaMxpU0CNLGZKPBj/cTZtBtb0wunucTmmrm2Xb7P//y hPV0orkeVHrHHrzW6v6Lx0i+ALv+wM0fuWzJTvB1hTH1YS8oTYeeWyvkm/M6v6Um reO2UjwU3EgpnFu5LPC5+Y8gIyXnqgYHDHBqBwNOJjQy6fBj+P4NeCA= 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:Date:From:To:Subject:Message-ID:User-Agent:MIME-Version:Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=g1o9KCkdf3srj2LqPKs237+JW/v8lww51k9A2RjjU36DLnVamOuoHnDwPFEu9G bwf3rpr35sOnHr1Qq54XN6vfJoMRK2MBJmCP+I0s7Jl7rXGvCvxpBC0ULBOWbrs+ N7MWittPvzigyKQdrzAp1HAhDugN0MXqO4qmSzCj/1eXY=; Received: (qmail 25992 invoked by alias); 29 Jan 2013 13:13:23 -0000 Received: (qmail 25938 invoked by uid 22791); 29 Jan 2013 13:13:22 -0000 X-SWARE-Spam-Status: No, hits=-5.7 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 cantor2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 29 Jan 2013 13:13:16 +0000 Received: from relay2.suse.de (unknown [195.135.220.254]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by mx2.suse.de (Postfix) with ESMTP id 6F255A5271 for ; Tue, 29 Jan 2013 14:13:15 +0100 (CET) Date: Tue, 29 Jan 2013 14:13:15 +0100 (CET) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH] Fix PR56113 Message-ID: User-Agent: Alpine 2.00 (LNX 1167 2008-08-23) MIME-Version: 1.0 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 This reduces the amount of memory needed by PTA pointer unification which has quadratic memory requirements. It's very easy to improve the situation where a lot of pointer equivalences are present by not keeping duplicate bitmaps we unify using a hashtable already. This reduces the overhead of the testcase in the PR from requiring peak 2.5GB to 1.4MB instead. This doesn't change the fact that the algorithm is quadratic in its memory requirements (worst memory requirements when it doesn't produce anything useful in the end). Bootstrap and regtest running on x86_64-unknown-linux-gnu. I plan to install this on trunk and the 4.7 branch for the general memory-hog regressions. Richard. 2013-01-29 Richard Biener PR tree-optimization/56113 * tree-ssa-structalias.c (equiv_class_lookup): Also return the bitmap leader. (label_visit): Free duplicate bitmaps and record the leader instead. (perform_var_substitution): Adjust. Index: gcc/tree-ssa-structalias.c =================================================================== --- gcc/tree-ssa-structalias.c (revision 195532) +++ gcc/tree-ssa-structalias.c (working copy) @@ -1907,10 +1908,10 @@ equiv_class_label_eq (const void *p1, co } /* Lookup a equivalence class in TABLE by the bitmap of LABELS it - contains. */ + contains. Sets *REF_LABELS to the bitmap LABELS is equivalent to. */ static unsigned int -equiv_class_lookup (htab_t table, bitmap labels) +equiv_class_lookup (htab_t table, bitmap labels, bitmap *ref_labels) { void **slot; struct equiv_class_label ecl; @@ -1921,9 +1922,18 @@ equiv_class_lookup (htab_t table, bitmap slot = htab_find_slot_with_hash (table, &ecl, ecl.hashcode, NO_INSERT); if (!slot) - return 0; + { + if (ref_labels) + *ref_labels = NULL; + return 0; + } else - return ((equiv_class_label_t) *slot)->equivalence_class; + { + equiv_class_label_t ec = (equiv_class_label_t) *slot; + if (ref_labels) + *ref_labels = ec->labels; + return ec->equivalence_class; + } } @@ -2123,14 +2133,21 @@ label_visit (constraint_graph_t graph, s if (!bitmap_empty_p (graph->points_to[n])) { + bitmap ref_points_to; unsigned int label = equiv_class_lookup (pointer_equiv_class_table, - graph->points_to[n]); + graph->points_to[n], + &ref_points_to); if (!label) { label = pointer_equiv_class++; equiv_class_add (pointer_equiv_class_table, label, graph->points_to[n]); } + else + { + BITMAP_FREE (graph->points_to[n]); + graph->points_to[n] = ref_points_to; + } graph->pointer_label[n] = label; } } @@ -2190,7 +2223,7 @@ perform_var_substitution (constraint_gra /* Look up the location equivalence label if one exists, or make one otherwise. */ label = equiv_class_lookup (location_equiv_class_table, - pointed_by); + pointed_by, NULL); if (label == 0) { label = location_equiv_class++;