From patchwork Thu Aug 17 09:28:56 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 802453 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-460483-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="uJVt4/HU"; dkim-atps=neutral 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 3xY1BG1XVlz9t3B for ; Thu, 17 Aug 2017 19:29:09 +1000 (AEST) 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:subject:message-id:mime-version:content-type; q=dns; s= default; b=W8uudqmGAMpAKUnFrBkhyZ7CQZIRAszEAv1thZG9rA7vwX8KMZdbZ GM3uq6tpHcguvHqRyh5l1cv4RkcRdmipG6KBm6R89HG6ox2qXkYCeVe0UzZ8jSWY Q/kbmzqBYL3xSVqgOHu5HOIek36rELhwnzfPzKALaj/7c3fV9NqZ3c= 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:subject:message-id:mime-version:content-type; s= default; bh=Ku8Pkq05FypyXCC7LsLqcNrP0wg=; b=uJVt4/HU/WjVz2QSHfmx 8C7LGUPkxZJG463vsUfDMYNRYm/Xmt3TLtETLaFRWbBRlQmxe6vW3vdjb/CimJo+ Re8SQvqlU/ouCJ9gspXNVPkoRZD0ONsfdoFyVNiRl9BFniWCJlZus4dA6xpCGtpX lWJkjXGy+j1Bx0l8TZAEfCU= Received: (qmail 19372 invoked by alias); 17 Aug 2017 09:29:01 -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 19337 invoked by uid 89); 17 Aug 2017 09:29:00 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-11.9 required=5.0 tests=BAYES_00, GIT_PATCH_2, GIT_PATCH_3, RP_MATCHES_RCVD, SPF_PASS autolearn=ham version=3.3.2 spammy=Hx-languages-length:1898 X-HELO: mx1.suse.de Received: from mx2.suse.de (HELO mx1.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 17 Aug 2017 09:28:59 +0000 Received: from relay2.suse.de (charybdis-ext.suse.de [195.135.220.254]) by mx1.suse.de (Postfix) with ESMTP id 02FC8AF5A for ; Thu, 17 Aug 2017 09:28:56 +0000 (UTC) Date: Thu, 17 Aug 2017 11:28:56 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH] Speed up PTA solving Message-ID: User-Agent: Alpine 2.20 (LSU 67 2015-01-07) MIME-Version: 1.0 The following patch resulted from PR81827 analysis where I was on the wrong track initially. It still results in a small speedup because we avoid useless duplicate work in case nodes are unified and reduce the number of graph edges. Bootstrapped on x86_64-unknown-linux-gnu, testing in progress. Richard. 2017-08-17 Richard Biener * tree-ssa-structalias.c (solve_graph): When propagating to successors update the graphs succ edges and avoid duplicate work. Index: gcc/tree-ssa-structalias.c =================================================================== --- gcc/tree-ssa-structalias.c (revision 251119) +++ gcc/tree-ssa-structalias.c (working copy) @@ -2759,20 +2759,35 @@ solve_graph (constraint_graph_t graph) unsigned eff_escaped_id = find (escaped_id); /* Propagate solution to all successors. */ + unsigned to_remove = ~0U; EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 0, j, bi) { - bitmap tmp; - bool flag; - + if (to_remove != ~0U) + { + bitmap_clear_bit (graph->succs[i], to_remove); + to_remove = ~0U; + } unsigned int to = find (j); - tmp = get_varinfo (to)->solution; - flag = false; - + if (to != j) + { + /* Update the succ graph, avoiding duplicate + work. */ + to_remove = j; + if (! bitmap_set_bit (graph->succs[i], to)) + continue; + /* We eventually end up processing 'to' twice + as it is undefined whether bitmap iteration + iterates over bits set during iteration. + Play safe instead of doing tricks. */ + } /* Don't try to propagate to ourselves. */ if (to == i) continue; + bitmap tmp = get_varinfo (to)->solution; + bool flag = false; + /* If we propagate from ESCAPED use ESCAPED as placeholder. */ if (i == eff_escaped_id) @@ -2783,6 +2798,8 @@ solve_graph (constraint_graph_t graph) if (flag) bitmap_set_bit (changed, to); } + if (to_remove != ~0U) + bitmap_clear_bit (graph->succs[i], to_remove); } } }