From patchwork Tue Dec 8 06:15:38 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jeff Law X-Patchwork-Id: 553811 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 6DD8C140213 for ; Tue, 8 Dec 2015 17:16:02 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=BAYnSCzp; 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:to :from:subject:message-id:date:mime-version:content-type; q=dns; s=default; b=eiWCGwykvoYjez7chhWwflhUXT7Bj9ZCr4FoNibphB/fBuXQG0 RjhCjRI8LPWPws2R0x0261CgzURcEJNBPxm0BRX0IsbKBO1sXoOX7VWI6gidNxCC kEHijw+Wpq4mOnWxOml+zxJIpbBrSDcvn1OkvDYUxVVFDOFdhQCcjC1wQ= 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:to :from:subject:message-id:date:mime-version:content-type; s= default; bh=e4GI0POPtHHumwQcz0ojuX82Sxg=; b=BAYnSCzp2Cl+GIYH+iCD iX+/mlKd8WU6JPedYhG/TmVcL4MYrrwMWAEJVnoABEHSzw20FmrcvBeIiu6pvSrB J+oei+m/0UU2qOXdb/7W0bTE4+8dRS1xTHoxOmW4pV1C20F4r+EFORnQlJG/p5UQ RgfYLjK8N5OP8kVLzg1sp1I= Received: (qmail 88109 invoked by alias); 8 Dec 2015 06:15:42 -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 88003 invoked by uid 89); 8 Dec 2015 06:15:41 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.7 required=5.0 tests=AWL, BAYES_00, SPF_HELO_PASS, T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 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; Tue, 08 Dec 2015 06:15:40 +0000 Received: from int-mx10.intmail.prod.int.phx2.redhat.com (int-mx10.intmail.prod.int.phx2.redhat.com [10.5.11.23]) by mx1.redhat.com (Postfix) with ESMTPS id 4D1778C1A8 for ; Tue, 8 Dec 2015 06:15:39 +0000 (UTC) Received: from localhost.localdomain (ovpn-113-32.phx2.redhat.com [10.3.113.32]) by int-mx10.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id tB86FcCS030142 for ; Tue, 8 Dec 2015 01:15:39 -0500 To: gcc-patches@gcc.gnu.org From: Jeff Law Subject: [RFA] [PATCH] [PR tree-optimization/68619] Avoid direct cfg cleanups in tree-ssa-dom.c [2/3] Message-ID: <5666758A.7030608@redhat.com> Date: Mon, 7 Dec 2015 23:15:38 -0700 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.3.0 MIME-Version: 1.0 X-IsSubscribed: yes This patch tweaks tree-ssa-dom.c to use the new capability in the dom walker. Additionally: The code to remove jump threading paths now runs after the walk is finished rather than when the conditional is optimized. The code which optimizes conditionals replaces the condition with a true/false condition and clears EDGE_EXECUTABLE. When we try to find equivalences from PHIs, we ignore a PHI arg associated with an unexecutable edge. When we look for blocks that have a single incoming edge, ignoring loop edges, we ignore edges that are not executable. That's enough to get all the benefits of the current implementation on the trunk, and as slightly better code than the trunk in certain cases. Obviously if we twiddle the member names in patch #1, then this patch will need corresponding trivial updates. Jeff commit 89a7f78005a5ec4788383ecd44474c85103693b5 Author: Jeff Law Date: Mon Dec 7 22:43:06 2015 -0700 PR tree-optimization/68619 * tree-ssa-dom.c (pass_dominator:execute): Use new methods from dom_walker to handle unreachable code. If a block has an unreachable edge, remove all jump threads through any successor of the affected block. (dom_opt_dom_walker::thread_across_edge): Do not thread across edges without EDGE_EXECUTABLE set. (record_equivalences_from_phis): Ignore alternatives if the edge does not have EDGE_EXECUTABLE set. (single_incoming_edge_ignoring_loop_edges): Similarly. (dom_opt_dom_walker::before_dom_children): Use new methods from dom_walker to handle unreachable code. (dom_opt_dom_walker::after_dom_children): Similarly. (optimize_stmt): If a gimple_code has a compile-time constant condition, clear EDGE_EXECUTABLE on the non-taken edges. Also change the condition to true/false as necessary. diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c index aeb726c..c48951e 100644 --- a/gcc/tree-ssa-dom.c +++ b/gcc/tree-ssa-dom.c @@ -609,8 +609,39 @@ pass_dominator::execute (function *fun) dom_opt_dom_walker walker (CDI_DOMINATORS, const_and_copies, avail_exprs_stack); + walker.init_edge_executable (cfun); walker.walk (fun->cfg->x_entry_block_ptr); + /* Look for blocks where we cleared EDGE_EXECUTABLE on an outgoing + edge. When found, remove jump threads which contain any outgoing + edge from the affected block. */ + if (cfg_altered) + { + FOR_EACH_BB_FN (bb, fun) + { + edge_iterator ei; + edge e; + + /* First see if there are any edges without EDGE_EXECUTABLE + set. */ + bool found = false; + FOR_EACH_EDGE (e, ei, bb->succs) + { + if ((e->flags & EDGE_EXECUTABLE) == 0) + { + found = true; + break; + } + } + + /* If there were any such edges found, then remove jump threads + containing any edge leaving BB. */ + if (found) + FOR_EACH_EDGE (e, ei, bb->succs) + remove_jump_threads_including (e); + } + } + { gimple_stmt_iterator gsi; basic_block bb; @@ -893,6 +924,11 @@ record_temporary_equivalences (edge e, void dom_opt_dom_walker::thread_across_edge (edge e) { + /* If E is not executable, then there's no reason to bother + threading across it. */ + if ((e->flags & EDGE_EXECUTABLE) == 0) + return; + if (! m_dummy_cond) m_dummy_cond = gimple_build_cond (NE_EXPR, @@ -951,6 +987,11 @@ record_equivalences_from_phis (basic_block bb) if (lhs == t) continue; + /* If the associated edge is not marked as executable, then it + can be ignored. */ + if ((gimple_phi_arg_edge (phi, i)->flags & EDGE_EXECUTABLE) == 0) + continue; + t = dom_valueize (t); /* If we have not processed an alternative yet, then set @@ -997,6 +1038,10 @@ single_incoming_edge_ignoring_loop_edges (basic_block bb) if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest)) continue; + /* We can safely ignore edges that are not executable. */ + if ((e->flags & EDGE_EXECUTABLE) == 0) + continue; + /* If we have already seen a non-loop edge, then we must have multiple incoming non-loop edges and thus we return NULL. */ if (retval) @@ -1307,6 +1352,14 @@ dom_opt_dom_walker::before_dom_children (basic_block bb) m_avail_exprs_stack->push_marker (); m_const_and_copies->push_marker (); + /* If BB is not reachable, then propagate that property to edges, but + do not process this block any further. */ + if (!this->bb_reachable (cfun, bb)) + { + this->propagate_unreachable_to_edges (bb, dump_file, dump_flags); + return; + } + record_equivalences_from_incoming_edge (bb, m_const_and_copies, m_avail_exprs_stack); @@ -1339,6 +1392,16 @@ dom_opt_dom_walker::after_dom_children (basic_block bb) { gimple *last; + /* If this block is not reachable, then there's nothing to do here. + However, make sure to restore the tables to their proper state. */ + if (!this->bb_reachable (cfun, bb)) + { + this->maybe_clear_unreachable_dom (bb); + m_avail_exprs_stack->pop_to_marker (); + m_const_and_copies->pop_to_marker (); + return; + } + /* If we have an outgoing edge to a block with multiple incoming and outgoing edges, then we may be able to thread the edge, i.e., we may be able to statically determine which of the outgoing edges @@ -1852,22 +1915,25 @@ optimize_stmt (basic_block bb, gimple_stmt_iterator si, edge taken_edge = find_taken_edge (bb, val); if (taken_edge) { - - /* We need to remove any queued jump threads that - reference outgoing edges from this block. */ + /* Clear the EXECUTABLE flag on the other edges. */ edge_iterator ei; edge e; FOR_EACH_EDGE (e, ei, bb->succs) - remove_jump_threads_including (e); - - /* Now clean up the control statement at the end of - BB and remove unexecutable edges. */ - remove_ctrl_stmt_and_useless_edges (bb, taken_edge->dest); + { + if (e != taken_edge) + e->flags &= ~EDGE_EXECUTABLE; + } - /* Fixup the flags on the single remaining edge. */ - taken_edge->flags - &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_ABNORMAL); - taken_edge->flags |= EDGE_FALLTHRU; + /* And fix the condition to be either true or false. */ + if (gimple_code (stmt) == GIMPLE_COND) + { + if (integer_zerop (val)) + gimple_cond_make_false (as_a (stmt)); + else if (integer_onep (val)) + gimple_cond_make_true (as_a (stmt)); + else + gcc_unreachable (); + } /* Further simplifications may be possible. */ cfg_altered = true;