From patchwork Tue Sep 17 17:27:53 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jeff Law X-Patchwork-Id: 275515 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 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id 874302C00D0 for ; Wed, 18 Sep 2013 03:41:07 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:subject:content-type; q= dns; s=default; b=fzz8BIhEIxaWLeFGnr3cP3xM2XWmgHc2RgCf3Q+tgyy+hE hBFfpuLltNvcVHA1qSlE/yvUup9a1TtPWzNHmP6WXNcc5nQToddc7eu5h6t0/q6y YggXERy+ihfwBBAeaB9cKjbwBONBOZa0Y4bZulBzbkKgZikX52IT5u4FHVcAw= 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 :message-id:date:from:mime-version:to:subject:content-type; s= default; bh=XD4zvEmTOthJtgt7yyg5gRGJsSM=; b=ie8q3KnFWe4QljgU3HS3 XPw4aenKzNZjJ1BVH4e+CSYTItShJ9PRZUk8JceZtizrxmqBUHAbVL3KYWPf/2sP NjMNiCwd3C8TjyfIAs50ZfFCXS1xQsl++Dq5jDeCfCuaqP7+BTGKErlZizdsbkCN zX5Hl+giAmSuf3KiY/cS9Ts= Received: (qmail 9139 invoked by alias); 17 Sep 2013 17:40:59 -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 20810 invoked by uid 89); 17 Sep 2013 17:27:57 -0000 Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 17 Sep 2013 17:27:57 +0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.5 required=5.0 tests=AWL, BAYES_00, RP_MATCHES_RCVD autolearn=ham version=3.3.2 X-HELO: mx1.redhat.com Received: from int-mx02.intmail.prod.int.phx2.redhat.com (int-mx02.intmail.prod.int.phx2.redhat.com [10.5.11.12]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id r8HHRrgW007489 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Tue, 17 Sep 2013 13:27:53 -0400 Received: from stumpy.slc.redhat.com (ovpn-113-163.phx2.redhat.com [10.3.113.163]) by int-mx02.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id r8HHRrL9027933 for ; Tue, 17 Sep 2013 13:27:53 -0400 Message-ID: <52389119.3040403@redhat.com> Date: Tue, 17 Sep 2013 11:27:53 -0600 From: Jeff Law User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130805 Thunderbird/17.0.8 MIME-Version: 1.0 To: gcc-patches Subject: [PATCH]Fix missed propagation opportunity in DOM X-IsSubscribed: yes This is a repost with fixes to avoid the phase-ordering problem exposed by 58387 and 58340. I've included the testcase for 58387. --- I recently noticed that we were failing to propagate edge equivalences into PHI arguments in non-dominated successors. The case loos like this: ;; basic block 11, loop depth 0, count 0, freq 160, maybe hot ;; prev block 10, next block 12, flags: (NEW, REACHABLE) ;; pred: 10 [50.0%] (FALSE_VALUE,EXECUTABLE) _257 = di_13(D)->comps; _258 = (long unsigned int) _255; _259 = _258 * 24; p_260 = _257 + _259; _261 = _255 + 1; di_13(D)->next_comp = _261; if (p_260 != 0B) goto ; else goto ; ;; succ: 12 [100.0%] (TRUE_VALUE,EXECUTABLE) ;; 13 (FALSE_VALUE,EXECUTABLE) ;; basic block 12, loop depth 0, count 0, freq 272, maybe hot ;; Invalid sum of incoming frequencies 160, should be 272 ;; prev block 11, next block 13, flags: (NEW, REACHABLE) ;; pred: 11 [100.0%] (TRUE_VALUE,EXECUTABLE) p_260->type = 37; p_260->u.s_builtin.type = _139; ;; succ: 13 [100.0%] (FALLTHRU,EXECUTABLE) ;; basic block 13, loop depth 0, count 0, freq 319, maybe hot ;; Invalid sum of incoming frequencies 432, should be 319 ;; prev block 12, next block 14, flags: (NEW, REACHABLE) ;; pred: 110 [100.0%] (FALLTHRU) ;; 12 [100.0%] (FALLTHRU,EXECUTABLE) ;; 11 (FALSE_VALUE,EXECUTABLE) # _478 = PHI <0B(110), p_260(12), p_260(11)> ret = _478; _142 = di_13(D)->expansion; _143 = _478->u.s_builtin.type; In particular note block 11 does *not* dominate block 13. However, we know that when we traverse the edge 11->13 that p_260 will have the value zero, which should be propagated into the PHI node. After fixing the propagation with the attached patch we have _478 = PHI <0B(110), p_260(12), 0B(11)> I have other code which then discovers the unconditional NULL pointer dereferences when we traverse 110->13 or 11->13 and isolates those paths. That in turn allows blocks 12 and 13 to be combined, which in turn allows discovery of additional CSE opportunities. Bootstrapped and regression tested on x86_64-unknown-linux-gnu. Applied to the trunk. * gcc.c-torture/execute/pr58387.c: New test. * tree-ssa-dom.c (cprop_into_successor_phis): Also propagate edge implied equivalences into successor phis. * tree-ssa-threadupdate.c (phi_args_equal_on_edges): Moved into here from tree-ssa-threadedge.c. (mark_threaded_blocks): When threading through a joiner, if both successors of the joiner's clone reach the same block, verify the PHI arguments are equal. If not, cancel the jump threading request. * tree-ssa-threadedge.c (phi_args_equal_on_edges): Moved into tree-ssa-threadupdate.c (thread_across_edge): Don't check PHI argument equality when threading through joiner block here. diff --git a/gcc/testsuite/gcc.c-torture/execute/pr58387.c b/gcc/testsuite/gcc.c-torture/execute/pr58387.c new file mode 100644 index 0000000..74c32df --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/execute/pr58387.c @@ -0,0 +1,11 @@ +extern void abort(void); + +int a = -1; + +int main () +{ + int b = a == 0 ? 0 : -a; + if (b < 1) + abort (); + return 0; +} diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c index e02a566..bf75135 100644 --- a/gcc/tree-ssa-dom.c +++ b/gcc/tree-ssa-dom.c @@ -1642,6 +1642,28 @@ cprop_into_successor_phis (basic_block bb) if (gsi_end_p (gsi)) continue; + /* We may have an equivalence associated with this edge. While + we can not propagate it into non-dominated blocks, we can + propagate them into PHIs in non-dominated blocks. */ + + /* Push the unwind marker so we can reset the const and copies + table back to its original state after processing this edge. */ + const_and_copies_stack.safe_push (NULL_TREE); + + /* Extract and record any simple NAME = VALUE equivalences. + + Don't bother with [01] = COND equivalences, they're not useful + here. */ + struct edge_info *edge_info = (struct edge_info *) e->aux; + if (edge_info) + { + tree lhs = edge_info->lhs; + tree rhs = edge_info->rhs; + + if (lhs && TREE_CODE (lhs) == SSA_NAME) + record_const_or_copy (lhs, rhs); + } + indx = e->dest_idx; for ( ; !gsi_end_p (gsi); gsi_next (&gsi)) { @@ -1667,6 +1689,8 @@ cprop_into_successor_phis (basic_block bb) && may_propagate_copy (orig_val, new_val)) propagate_value (orig_p, new_val); } + + restore_vars_to_original_value (); } } diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c index 42474f1..47db280 100644 --- a/gcc/tree-ssa-threadedge.c +++ b/gcc/tree-ssa-threadedge.c @@ -841,28 +841,6 @@ thread_around_empty_blocks (edge taken_edge, return false; } -/* E1 and E2 are edges into the same basic block. Return TRUE if the - PHI arguments associated with those edges are equal or there are no - PHI arguments, otherwise return FALSE. */ - -static bool -phi_args_equal_on_edges (edge e1, edge e2) -{ - gimple_stmt_iterator gsi; - int indx1 = e1->dest_idx; - int indx2 = e2->dest_idx; - - for (gsi = gsi_start_phis (e1->dest); !gsi_end_p (gsi); gsi_next (&gsi)) - { - gimple phi = gsi_stmt (gsi); - - if (!operand_equal_p (gimple_phi_arg_def (phi, indx1), - gimple_phi_arg_def (phi, indx2), 0)) - return false; - } - return true; -} - /* We are exiting E->src, see if E->dest ends with a conditional jump which has a known value when reached via E. @@ -1021,18 +999,9 @@ thread_across_edge (gimple dummy_cond, record the jump threading opportunity. */ if (found) { - edge tmp; - /* If there is already an edge from the block to be duplicated - (E2->src) to the final target (E3->dest), then make sure that - the PHI args associated with the edges E2 and E3 are the - same. */ - tmp = find_edge (taken_edge->src, path[path.length () - 1]->dest); - if (!tmp || phi_args_equal_on_edges (tmp, path[path.length () - 1])) - { - propagate_threaded_block_debug_into (path[path.length () - 1]->dest, - taken_edge->dest); - register_jump_thread (path, true); - } + propagate_threaded_block_debug_into (path[path.length () - 1]->dest, + taken_edge->dest); + register_jump_thread (path, true); } path.release(); diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c index d755266..4131128 100644 --- a/gcc/tree-ssa-threadupdate.c +++ b/gcc/tree-ssa-threadupdate.c @@ -1147,6 +1147,28 @@ fail: return false; } +/* E1 and E2 are edges into the same basic block. Return TRUE if the + PHI arguments associated with those edges are equal or there are no + PHI arguments, otherwise return FALSE. */ + +static bool +phi_args_equal_on_edges (edge e1, edge e2) +{ + gimple_stmt_iterator gsi; + int indx1 = e1->dest_idx; + int indx2 = e2->dest_idx; + + for (gsi = gsi_start_phis (e1->dest); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple phi = gsi_stmt (gsi); + + if (!operand_equal_p (gimple_phi_arg_def (phi, indx1), + gimple_phi_arg_def (phi, indx2), 0)) + return false; + } + return true; +} + /* Walk through the registered jump threads and convert them into a form convenient for this pass. @@ -1219,6 +1241,46 @@ mark_threaded_blocks (bitmap threaded_blocks) } } + /* If we have a joiner block (J) which has two successors S1 and S2 and + we are threading though S1 and the final destination of the thread + is S2, then we must verify that any PHI nodes in S2 have the same + PHI arguments for the edge J->S2 and J->S1->...->S2. + + We used to detect this prior to registering the jump thread, but + that prohibits propagation of edge equivalences into non-dominated + PHI nodes as the equivalency test might occur before propagation. + + This works for now, but will need improvement as part of the FSA + optimization. + + Note since we've moved the thread request data to the edges, + we have to iterate on those rather than the threaded_edges vector. */ + EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi) + { + bb = BASIC_BLOCK (i); + FOR_EACH_EDGE (e, ei, bb->preds) + { + if (e->aux) + { + bool have_joiner = THREAD_TARGET2 (e) != NULL; + + if (have_joiner) + { + basic_block joiner = e->dest; + edge final_edge = THREAD_TARGET2 (e); + basic_block final_dest = final_edge->dest; + edge e2 = find_edge (joiner, final_dest); + + if (e2 && !phi_args_equal_on_edges (e2, final_edge)) + { + free (e->aux); + e->aux = NULL; + } + } + } + } + } + /* If optimizing for size, only thread through block if we don't have to duplicate it or it's an otherwise empty redirection block. */